current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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 );
        }
    }
share|improve this question
1  
Welcome to CodeReview, ironicaldiction. I hope you get some fine answers. –  Legato 2 days ago
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 2 days ago
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. –  EBrown yesterday
    
thanks...will do –  ironicaldiction yesterday

2 Answers 2

up vote 8 down vote

  • 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.
share|improve this answer
up vote 3 down vote

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...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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