String related problem from CodingBat

Question

I was trying this problem and I was wondering if there is a way to check for the edge cases inside the for-loop.

The problem statement:

We'll say that a lowercase 'g' in a string is "happy" if there is another 'g' immediately to its left or right. Return true if all the g's in the given string are happy.

Here I am starting the loop from index 1 as I need to look back and I don't want an ArrayIndexOutOfBounds exception. The same applies for the end edge case where I need to look the following index.

To avoid this problem I'm checking these cases right after I've checked all the others, but it doesn't feel quite right. Is there a way to do it in a more compact way?

public boolean gHappy(String str) {

   if(str.length() == 1 && str.charAt(0) == 'g') return false; 
   if(str.length() == 0) return true;

   for(int i = 1; i < str.length() - 1; i ++) {
     if(str.charAt(i) == 'g') {
       if(str.charAt(i - 1) != 'g' && str.charAt(i + 1) != 'g') return false;     
     } 
   }
 // edge cases (start-end)
 if(str.charAt(0) == 'g' && str.charAt(1) != 'g') return false;
 if(str.charAt(str.length() - 1) == 'g' && str.charAt(str.length() - 2) != 'g') return false;

 return true;
}

Answer 1

There's several 'special cases' in your code.

• String of length 1
• String of length 0
• 'g' at start of String
• 'g' at end of String

I'd recommend getting rid of these special cases.

To do this, you can check for special conditions inside the for-loop.

Loop through all the positions in the string, and check if there is a 'g' on that position. If it is, then check if the position is more than 0 (i.e. it has a char in front of it) or if the position is less than str.length - 1 (i.e. it has a char after it).

The details about how to write this can be done in oh so many ways, but here is what I would end up with:

for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    if (ch == 'g') {
        if (i > 0 && str.charAt(i - 1) == ch) {
            continue;
        }
        if (i < str.length() - 1 && str.charAt(i + 1) == ch) {
            continue;
        }
        return false;
    }
}

return true;

Answer 2

You can remove two if-statements altogether if you think about it! Also, you don't even need your first edge-case if you do this:

 public boolean gHappy(String str) {

   if(str.length() == 1 && str.charAt(0) == 'g') return false; 
   if(str.length() == 0) return true;

   for(int i = 1; i < str.length() - 1; i ++) {
     if(str.charAt(i) == 'g' && ((str.charAt(i - 1) != 'g' && str.charAt(i + 1) != 'g'))){
       return false;     
     } 
   }

   // edge cases (start-end)
   if(str.charAt(str.length() - 1) == 'g' && str.charAt(str.length() - 2) != 'g'){
      return false;
   }
   return true;
 }

Also, you should always use brackets in your statements, even if it's just one line. Not using brackets makes things harder for other programmers to read your code and increases the probability that unintended bugs arise.

Answer 3

The right tool for the right job:

Regular Expressions

A Regular Expressions often known as Regexp or Regex is a pattern that may or may not match a text according to some rules.

The simplest of Regexes is the literal one:

"foo".match("f")

An alphabetic character will match itself.

There are many many rules and patterns that you can use and I suggest learning them, anyway we only need this very basic and another:

[^<character(s)>]

that matches everything but the character(s).

For example [^a] matches everything but a.

It is your challange

This two tools will allow you to solve this problem using Regexp, just for future reference I include the code (in Ruby but Regexes are pretty similar between languages) that solves the problem (tested), but please think about this for yourself:

def geppy(string) not string.match("[^g]g[^g]") end

Fixing edge cases in a non-elegant manner:

def geppy(string)
  return false if string.length == 1
  return false if string.length == 2 && string != 'gg'
  return (not string.match("[^g]g[^g]"))
end

Answer 4

Return true if all the g's in the given string are happy.

I actually dispute that if there are no g's in a string, then happiness cannot exist and this function should return false. Unfortunately, the test case for an empty string is true... so I guess we have to work with it.

for(int i = 1; i < str.length() - 1; i ++) {...}

Most standards ensure that if, else, for has a space between the keyword and the argument list. This helps with readability by distinguishing these keywords from regular functions.

for (int i = 1; i < str.length() - 1; i++) {...}

Be explicit with your expressions. Evaluating your conditional on every loop may sometimes be needed, but those cases are rare. Most of the time, we just need to evaluate once and compare to a constant.

for (int i = 1, strlen = str.length() - 1; i < strlen; i++) {...}

if(str.charAt(0) == 'g' && str.charAt(1) != 'g') return false;
if(str.charAt(str.length() - 1) == 'g' && str.charAt(str.length() - 2) != 'g') return false;

Evaluate your preconditions as early as possible before you do the majority of the work.

Avoid magic values. Our happy character happens to be specialized to 'g' for this problem, but we can still write the general solution for it and call the general solution from our specialized function.

Putting it all together (including a small optimization that jumps ahead on connected matches),

public boolean gHappy(String str) {
  return happy(str, 'g');
}

public boolean happy(String str, char happyCh) {
  if (str.length() == 0) {
    return true;
  }
  if (str.length() == 1) {
    return false;
  }
  if (str.charAt(0) == happyCh && str.charAt(1) != happyCh) {
    return false;
  }
  if (str.charAt(str.length() - 1) == happyCh &&
      str.charAt(str.length() - 2) != happyCh) {
    return false;
  }
  for (int i = 1, size = str.length() - 1; i < size; ++i) {
    if (str.charAt(i) != happyCh) {
      continue;
    }
    if (str.charAt(i - 1) != happyCh && str.charAt(i + 1) != happyCh) {
      return false;
    }
    // Since all the connecting 'g's are happy, advance until 
    // a non-'g' is encountered.
    while (i < size && str.charAt(i) == happyCh) {
      ++i;
    }
  }
  return true;
}