I'm a little rusty in Java, but I'm using it to get ready for interviews. Here's the problem description from HackerRank:

Problem Statement

Suppose you have a string \$S\$ which has length \$N\$ and is indexed from \$0\$ to \$N−1\$. String \$R\$ is the reverse of the string \$S\$. The string \$S\$ is funny if the condition \$|S_i−S_{i−1}|=|R_i−R_{i−1}|\$ is true for every \$i\$ from 1 to \$N−1\$.

(Note: Given a string str, stri denotes the ascii value of the ith character (0-indexed) of str. |x| denotes the absolute value of an integer x)

Input Format

First line of the input will contain an integer T. T testcases follow. Each of the next T lines contains one string S.

Constraints

  • \$1 \le T \le 10\$
  • \$2 \le\$ length of S \$\le 10000\$

Output Format

For each string, print Funny or Not Funny in separate lines.

This passing solution took me about 20 minutes, so that might be a bit long given the difficulty of the problem. I'm open to critiques on my speed too.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    private static boolean isFunny (String s)
    {
        String rev = reverse(s);
        boolean stillEq = true;
        for (int i = 2; i < s.length() && stillEq; ++i)
        {
            int comp = (int)s.charAt(i) - (int)s.charAt(i-1);
            int comp2 = (int)rev.charAt(i) - (int)rev.charAt(i-1);
            stillEq = Math.abs(comp) == Math.abs(comp2);
        }

        if (stillEq)
            return true;
        else
            return false;
    }

    private static String reverse (String s)
    {
        if (s.length() > 0)
            return s.charAt(s.length()-1) + reverse(s.substring(0, s.length()-1));
        else
            return "";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tests = sc.nextInt();
        for (int i = 0; i < tests; ++i)
        {
            String out = isFunny(sc.next()) ? "Funny" : "Not Funny";
            System.out.println( out );
        }
    }
  • 1
    Welcome to CodeReview, ironicaldiction. I hope you get some fine answers. – Legato Sep 24 '15 at 3:14
  • 1
    Wouldn't it be easier to just keep two counters and not actually reverse the string? Seems a bit unnecessary to physically reverse when you can easily compute the math involved. – corsiKa Sep 24 '15 at 7:01
  • 1
    Please do not edit your question to include changes you made due to answers. If you wish to indicate what changes you made, you should post a self-answer citing the answers you used to make your changes, or a new question if you still want improvements on your (new) code. – 202_accepted Sep 25 '15 at 18:16
up vote 12 down vote accepted
  • Bug

    The main loop starts at i = 2. That is, s.charAt(1) - s.charAt(0) is never attended to. Suspicious, isn't it?

  • Naming

    A name comp (and comp2) presumes that it carries some information about comparison. It obviously doesn't. diff and rdiff sound better.

  • Algorithm

    Reversal of the string just wastes time. You may work the same string from both directions simultaneously:

    for (int i = 1; i < s.length(); ++i) {
        diff = s.charAt(i) - s.charAt(i - 1);
        rdiff = s.charAt(s.length() - 1 - i) - s.charAt(s.length() - 1 - (i-1));
        ...
    
  • Returning the comparison result is an anti-pattern.

    return stillEq;
    

    achieves the same result as

    if (stillEq)
        return true;
    else
        return false;
    

    in a much cleaner way.

  • If you insist on reversing a string, better come up with an iterative method. Java cannot eliminate tail recursion.

What jumps out at me is:

private static String reverse (String s)
{
    if (s.length() > 0)
        return s.charAt(s.length()-1) + reverse(s.substring(0, s.length()-1));
    else
        return "";
}

This has two problems:

  1. it's recursive - Java doesn't handle tail optimisation and recursion is slow
  2. It makes a rather large number of copies - String.substring copies the underlying String
  3. it's very long

I would suggest:

private static String reverse (final String s) {
    return new StringBuilder(s).reverse().toString();
}

I would also suggest that you always use brackets for your if...else statements. It's generally accepted common practice and with good reason - the few lines that you save by not doing so lead to some very insidious bugs.

On an algorithmic note: why reverse the String at all? Use one loop and read the String both forwards and backwards simultaneously.

For further improvement, walk through a comparison manually:

s = abcdef    
rs = fedcba

Leads to 5 distinct tests:

  1. |b - a| == |e - f|
  2. |c - b| == |d - e|
  3. |d - c| == |c - d|
  4. |e - d| == |b - c|
  5. |f - e| == |a - b|

What do you notice about the pairs 1. <-> 5. and 2. <-> 4.? There is a simpler solution to this problem than brute force...

In addition to the other answers.

  • Let your IDE format your code instead of doing it by hand. This will avoid inconsistencies in spacing.
  • Use an early return instead of the stillEq variable. This will make your program faster.
  • Since the task talks about reading lines, you should use Scanner.nextLine instead of Scanner.next.
  • Write i++ instead of ++i. While they are completely equivalent to the compiler, the former style is much more common. (Using the latter style tells the informed reader that you come from a C++ background and you don't trust the compiler to generate efficient code no matter how you write it.)

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.