2.10 Implementing String Algorithms

1. Traversing a string

String algorithms work by string traversal: a loop visits each position, and substring takes out the part to test. A single character at index i is str.substring(i, i + 1). Indexes run from 0 to length() - 1.

String team = "Hawks";
for (int i = 0; i < team.length(); i++) {
    System.out.println(i + ": " + team.substring(i, i + 1));
}

Output:

0: H
1: a
2: w
3: k
4: s

Watch out (off by one): with i <= team.length(), the last pass asks for substring(5, 6) on a 5-letter string:

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

Output:

H
a
w
k
s
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: Range [5, 6) out of bounds for length 5

The five letters print, then the program crashes on the sixth pass. (The exact wording of the message depends on the Java version.)

2. Does a substring have a property?

There are standard string algorithms to find if one or more substrings have a particular property 2.10.A.1. Two kinds of question:

• “Is there any substring with the property?” Return true as soon as you find one; return false only after the loop.
• “Do all substrings have the property?” Return false as soon as one fails; return true only after the loop.

Does a word contain a double letter (the same letter twice in a row)? Each test compares the letter at i with the letter at i + 1, so the loop must stop before the last index.

public static boolean hasDoubleLetter(String word) {
    for (int i = 0; i < word.length() - 1; i++) {
        String here = word.substring(i, i + 1);
        String next = word.substring(i + 1, i + 2);
        if (here.equals(next)) {
            return true;
        }
    }
    return false;
}

System.out.println(hasDoubleLetter("balloon"));
System.out.println(hasDoubleLetter("planet"));
System.out.println(hasDoubleLetter(""));

Output:

true
false
false

Watch out: putting else { return false; } inside the loop would make the method stop after checking only the first pair, so "balloon" would return false.

Is every character a digit? "0123456789".indexOf(ch) is -1 when ch is not a digit.

public static boolean allDigits(String code) {
    for (int i = 0; i < code.length(); i++) {
        String ch = code.substring(i, i + 1);
        if ("0123456789".indexOf(ch) == -1) {
            return false;
        }
    }
    return true;
}

System.out.println(allDigits("2026"));
System.out.println(allDigits("20x6"));

Output:

true
false

3. Counting substrings that meet a criterion

There are standard string algorithms to determine the number of substrings that meet specific criteria 2.10.A.1. Count the vowels in a sentence:

String sentence = "Game over";
int vowels = 0;
for (int i = 0; i < sentence.length(); i++) {
    String ch = sentence.substring(i, i + 1);
    if ("aeiouAEIOU".indexOf(ch) >= 0) {
        vowels++;
    }
}
System.out.println("Vowels: " + vowels);

Output:

Vowels: 4

To count a pattern longer than one letter, use a window of that length. How many times does "an" appear in "banana"? The window substring(i, i + 2) needs i + 2 <= length(), so the loop condition is i <= word.length() - 2.

String word = "banana";
int count = 0;
for (int i = 0; i <= word.length() - 2; i++) {
    if (word.substring(i, i + 2).equals("an")) {
        count++;
    }
}
System.out.println(count);

Output:

2

i	substring(i, i + 2)	equals “an”?	count
0	ba	no	0
1	an	yes	1
2	na	no	1
3	an	yes	2
4	na	no	2

Watch out (String comparison with ==): this version compiles and runs, but == compares references, and every call to substring here returns a new String object.

String word = "banana";
int count = 0;
for (int i = 0; i < word.length(); i++) {
    if (word.substring(i, i + 1) == "a") {
        count++;
    }
}
System.out.println(count);

Output:

0

4. Reversing a string

There are standard string algorithms to create a new string with the characters reversed 2.10.A.1. Strings are immutable, so you build a new string. Adding each character to the front reverses the order:

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

Output:

edoc

i	letter	reversed after this iteration
0	c	c
1	o	oc
2	d	doc
3	e	edoc

The other way: traverse from the last index down to 0 and add each character to the end. Start at length() - 1, not length().

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

Output:

edoc

5. Combining the algorithms

Original algorithms often combine the standard ones. A palindrome reads the same forward and backward: reverse the word, then compare with equals.

public static boolean isPalindrome(String word) {
    String reversed = "";
    for (int i = 0; i < word.length(); i++) {
        reversed = word.substring(i, i + 1) + reversed;
    }
    return reversed.equals(word);
}

System.out.println(isPalindrome("level"));
System.out.println(isPalindrome("lever"));

Output:

true
false

Another combination: remove every space from a string by building a new one that skips spaces.

String phrase = "a b  c";
String result = "";
for (int i = 0; i < phrase.length(); i++) {
    String ch = phrase.substring(i, i + 1);
    if (!ch.equals(" ")) {
        result += ch;
    }
}
System.out.println(result + " (" + result.length() + " letters)");

Output:

abc (3 letters)