2.10 - Implementing String Algorithms

There are standard algorithm patterns for strings too:

Checking if one or more substrings have a certain property

Counting how many substrings meet a specific criteria

Building a new string with the characters reversed

Most string algorithms loop through the string by index, from 0 up to length() - 1. To get the letter at index i, use substring(i, i + 1), which gives it to you as a one-letter String (see 1.15).

Checking for a Property


// does the word contain a vowel?
String word = "hello";
boolean hasVowel = false;
for (int i = 0; i < word.length(); i++) {
    String letter = word.substring(i, i + 1);
    if (letter.equals("a") || letter.equals("e") || letter.equals("i")
            || letter.equals("o") || letter.equals("u")) {
        hasVowel = true;
    }
}
System.out.println(hasVowel); // true

For substrings longer than one letter, look at substring(i, i + n) for each starting index i. The last valid start is length() - n, so the loop condition is i <= word.length() - n. Going one past that throws a StringIndexOutOfBoundsException.


// does the word have the same letter twice in a row?
String word = "balloon";
boolean hasDouble = false;
for (int i = 0; i <= word.length() - 2; i++) {
    String pair = word.substring(i, i + 2);
    if (pair.substring(0, 1).equals(pair.substring(1))) {
        hasDouble = true;
    }
}
System.out.println(hasDouble); // true ("ll" and "oo")

If you only need to know whether a string contains a substring anywhere, indexOf does it in one step: word.indexOf("oo") != -1 is true when "oo" shows up somewhere in word.

Counting Substrings

Same loop, but add 1 to a counter each time a substring meets the condition:


// how many times does "an" appear in "banana"?
String str = "banana";
String target = "an";
int count = 0;
for (int i = 0; i <= str.length() - target.length(); i++) {
    if (str.substring(i, i + target.length()).equals(target)) {
        count++;
    }
}
System.out.println(count); // 2

This counts overlapping matches too. In "aaaa", the substring "aa" is counted 3 times (starting at index 0, 1, and 2).

Reversing a String

Loop from the last index down to 0 and add each letter to a new string. The original string never changes, since strings are immutable.


String original = "hello";
String reversed = "";
for (int i = original.length() - 1; i >= 0; i--) {
    reversed += original.substring(i, i + 1);
}
System.out.println(reversed); // olleh

You can also loop forward and add each letter to the front of the new string. Comparing the result to the original with equals checks for a palindrome (a word that reads the same backward):


String word = "racecar";
String backward = "";
for (int i = 0; i < word.length(); i++) {
    backward = word.substring(i, i + 1) + backward; // add each letter to the front
}
boolean isPalindrome = backward.equals(word);
System.out.println(isPalindrome); // true

Back Next