Aim for FiveComputer Science A

Unit 2 · Topic 2.10

2.10 Implementing String Algorithms

String algorithms walk through a string one index at a time and look at its pieces with substring. This topic covers the standard ones: checking for a property, counting matching substrings and building a reversed string, plus the index limits that keep you from running off the end.

Key terms

  • string traversal
  • substring
  • counting substrings
  • reversing a string

Traversing a string

To traverse a string means to visit its characters in order with a loop. The indexes run from 0 to length() - 1, so the standard loop is for (int i = 0; i < str.length(); i++).

The Java Quick Reference has no method that returns a single character, so take a one-letter substring: str.substring(i, i + 1). Compare it with equals, never ==.

Trace your loop on a short word first, writing each index under its letter. A handy trick for "is this letter one of these?" is indexOf: "aeiou".indexOf(letter) >= 0 is true exactly when letter is a lowercase vowel, because indexOf returns -1 when there's no match.

Looking at longer pieces

To look at every piece of length 2, use substring(i, i + 2). The last valid starting index is now length() - 2, because the piece ends at index i + 1. In general, for pieces of length k, the loop condition is i <= str.length() - k.

Get this wrong and the loop asks for characters that don't exist:

String s = "aaab"; for (int i = 0; i < s.length(); i++) { System.out.println(s.substring(i, i + 2)); }

For "aaab", this prints aa, aa, ab, and then, when i is 3, substring(3, 5) throws a StringIndexOutOfBoundsException.

Comparing neighbors works the same way. To compare each letter with the one after it, stop at length() - 1 so i + 1 is still valid.

Reversing a string

Strings are immutable, so you build a new one. Either loop backward and add each letter to the end of the result, or loop forward and add each letter to the front:

String word = "stop"; String result = ""; for (int i = 0; i < word.length(); i++) { result = word.substring(i, i + 1) + result; } System.out.println(result);

Both approaches turn "stop" into "pots". The same idea builds any new string: start with the empty string "" and add pieces in a loop, such as only the letters that aren't spaces.

Returning early

When a method only needs to know whether at least one piece has a property, it can return true the moment it finds one and return false after the loop. Don't put return false in an else inside the loop. That would quit after checking only the first piece.

Worked examples

Try each one yourself first, then open the solution.

  1. Example 1

    Write a method: counting vowels

    Write a method countVowels(String word) that returns the number of lowercase vowels (a, e, i, o, u) in word. One solution:public static int countVowels(String word) { int count = 0; for (int i = 0; i < word.length(); i++) { String letter = word.substring(i, i + 1); if ("aeiou".indexOf(letter) >= 0) { count++; } } return count; }

    Show the solution
    1. Step 1: This is the counting pattern from 2.9 applied to a string traversal.
    2. Step 2: Loop over every index from 0 to word.length() - 1 and take one letter with substring(i, i + 1).
    3. Step 3: "aeiou".indexOf(letter) is 0 to 4 for a vowel and -1 for anything else, so >= 0 means "is a vowel".
    4. Step 4: Check: "banana" has a, a, a, so 3. "rhythm" has no vowels, so 0. The empty string "" has length 0, so the loop runs zero times and the method returns 0.

    Answer: The method above; it returns 3 for "banana", 0 for "rhythm" and 0 for "".

  2. Example 2

    Counting overlapping pieces

    What does this code print?String s = "aaab"; int count = 0; for (int i = 0; i <= s.length() - 2; i++) { if (s.substring(i, i + 2).equals("aa")) { count++; } } System.out.println(count);

    Show the solution
    1. Step 1: s.length() is 4, so i runs from 0 to 2 (i <= 2).
    2. Step 2: i = 0: substring(0, 2) is "aa", a match. count is 1.
    3. Step 3: i = 1: substring(1, 3) is "aa", another match, overlapping the first. count is 2.
    4. Step 4: i = 2: substring(2, 4) is "ab", no match.

    Answer: It prints 2.

  3. Example 3

    Write a method: double letters

    Write a method hasDoubleLetter(String str) that returns true if str has two identical letters next to each other, such as the "ll" in "balloon". One solution:public static boolean hasDoubleLetter(String str) { for (int i = 0; i < str.length() - 1; i++) { if (str.substring(i, i + 1).equals(str.substring(i + 1, i + 2))) { return true; } } return false; }

    Show the solution
    1. Step 1: Each letter is compared with the next one, so i stops at str.length() - 2. The condition i < str.length() - 1 does that, and i + 2 never goes past the end.
    2. Step 2: As soon as a pair matches, the answer is known, so return true right away.
    3. Step 3: Only after every pair has been checked do you know the answer is false, so that return goes after the loop.
    4. Step 4: Check: "balloon" matches at "ll", so true. "apex" has no pair, so false. For "a", the loop condition is 0 < 0, so it runs zero times and returns false.

    Answer: The method above; it returns true for "balloon" and false for "apex" and "a".

Common mistakes

  • Looping to i < str.length() while using substring(i, i + 2). The last start index for a two-letter piece is length() - 2.
  • Comparing one-letter strings with ==. Use equals.
  • Writing return false inside the loop in an else, which stops after the first check.
  • Forgetting to store the result when building a string. result + letter; alone does nothing; write result += letter;.

On the exam

  • Part B of free-response Question 1 needs String methods. Expect to traverse a string with substring and indexOf, and be careful with the loop bounds.
  • Try your loop on a tiny string, like length 1 or the empty string, to check you won't go out of bounds.

Connected topics

Videos

Check yourself

4 questions on 2.10 Implementing String Algorithms. Pick an answer to see if you got it, and why.

Question 1 of 4

The following method is intended to return a string with the characters of s in reverse order. For example, reverseIt("stop") should return "pots".public static String reverseIt(String s) { String r = ""; /* missing code */ return r; }Which of the following can replace /* missing code */ so that the method works as intended?

Question 2 of 4

Consider the following code segment.String word = "bananas"; int count = 0; for (int i = 0; i <= word.length() - 3; i++) { if (word.substring(i, i + 3).equals("ana")) { count++; } } System.out.println(count);What is printed as a result of executing the code segment?

Question 3 of 4

Consider the following code segment.String s = "education"; int vowels = 0; for (int i = 0; i < s.length(); i++) { String letter = s.substring(i, i + 1); if ("aeiou".indexOf(letter) >= 0) { vowels++; } } System.out.println(vowels);What is printed as a result of executing the code segment?

Question 4 of 4

Consider the following code segment.String s = "cat"; String t = ""; for (int i = 0; i <= s.length(); i++) { t += s.substring(i, i + 1); } System.out.println(t);What is printed as a result of executing the code segment?

0 of 4 answered