Returning early from a loop

For a problem like countPs that we saw previously, we have to iterate over the entire string in order to correctly compute the answer. After all, the last character might be a 'p'. In many problems, we know the answer well before we reach the end of the data. As an example, take the simpler problem, "Is there a p in this string?"

Here is an incorrect attempt to solve it.

  public static boolean containsPBad(String s)
  {
    boolean answer = false;
    for (int i = 0; i < s.length(); i += 1)
    {
      if (s.charAt(i) == 'p')
      {
        answer = true;
      }
      else
      {
        answer = false;
      }
    }
    return answer;
  }

What goes wrong? Suppose you have a string like "apple". Trace through the execution and see what answer is returned. The problem is that once we find a P, we should stop searching for Ps, since the answer is now known. When the only task of a method is to produce the answer to an isolated question like this, the simplest strategy is to return from the method as soon as the answer is known.

  public static boolean containsP(String s)
  {
    for (int i = 0; i < s.length(); i += 1)
    {
      if (s.charAt(i) == 'p')
      {
        return true;
      }
    }
    
    // we only reach this statement if there wasn't a 'p'
    return false;
  }

In cases where it isn't practical to return from the method, you can also "break out" of a loop using the break statement.

  public static boolean containsPAlt(String s)
  {
    // assume false until we find a 'p'
    boolean answer = false;
    
    for (int i = 0; i < s.length(); i += 1)
    {
      if (s.charAt(i) == 'p')
      {
        // found one, "break" out of loop
        answer = true;
        break;
      }
    }

    return answer;
  }

Using break can be tricky, especially when there are nested loops or multiple variables being updated. In general, the form with the early return is preferable.

Moral of story

Whenever you go to write a loop, ask yourself: Do I always have to examine every piece of data, or can I stop early if I find what I'm looking for?