2.10 Implementing String algorithmsWalking through a String

The standard traversal visits every index once: for (int i = 0; i < s.length(); i++), and inside, String ch = s.substring(i, i + 1); is the character at index i, as a one-letter String. Compare it with equals, count it, or glue it onto a new String. Because Strings are immutable, "changing" a String always means building a new one, usually starting from the empty String "".
?Wait, why substring(i, i + 1) and not just one index?
1String w = "loop";2String rev = "";3int os = 0;4for (int i = 0; i < w.length(); i++)15{6 String ch = w.substring(i, i + 1);27 rev = ch + rev;38 if (ch.equals("o"))49 {10 os++;11 }12}13System.out.println(rev + " " + os);
- line 4 i goes 0 to length() - 1: every index once
- line 6 The character at index i, as a String
- line 7 Glue each new character on the front
- line 8 Compare Strings with equals
| i | ch | rev after | os after |
|---|---|---|---|
| 0 | "l" | "l" | 0 |
| 1 | "o" | "ol" | 1 |
| 2 | "o" | "ool" | 2 |
| 3 | "p" | "pool" | 2 |
| 4 | stop: 4 < 4 is false |
To look at pieces longer than one character, slide a window: s.substring(i, i + k) is the k characters starting at i. The last legal start is s.length() - k, so the loop runs while i <= s.length() - k. Going one step further throws a StringIndexOutOfBoundsException.
1String s = "banana";2int count = 0;3for (int i = 0; i <= s.length() - 2; i++)14{5 if (s.substring(i, i + 2).equals("an"))26 {7 count++;8 }9}10System.out.println(count);
- line 3 A 2-letter window: the last start is length() - 2
- line 5 Look at characters i and i + 1 together
indexOf gives a second way to find things. s.indexOf(t) is the first place t starts, or -1. To find every occurrence, find one, then keep only the part of the String after it and search again, until indexOf returns -1. Testing membership is another neat trick: "aeiou".indexOf(ch) is -1 exactly when ch is not a lowercase vowel.
?Wait, what does indexOf return when it finds nothing?
I thought about it. Show me
- Pattern: count, over a 2-character window. Start with int count = 0;.
- Each pair compares index i with index i + 1, so the last i is s.length() - 2. Loop: for (int i = 0; i < s.length() - 1; i++).
Why?
i + 1 must still be a legal index. With i < s.length(), the last pass would ask for index length(), which doesn't exist. - Inside: String a = s.substring(i, i + 1); and String b = s.substring(i + 1, i + 2);. If a.equals(b), count++.
Why?
Use equals, not ==, to compare Strings. - After the loop, return count;. Check "aaa": pairs at i = 0 and i = 1 both match, so 2. Check "": the loop runs while 0 < -1, which is false, so it returns 0 without crashing.
Answer:
public static int doubleLetters(String s)
{
int count = 0;
for (int i = 0; i < s.length() - 1; i++)
{
String a = s.substring(i, i + 1);
String b = s.substring(i + 1, i + 2);
if (a.equals(b))
{
count++;
}
}
return count;
}doubleLetters("bookkeeper") returns 3 and doubleLetters("aaa") returns 2 (checked under Java 17).
Stuck? Get a hint
- You compare each character with the next one. What's the last index that has a next one?
- Get both characters with substring(i, i + 1) and substring(i + 1, i + 2).
- Compare them with equals, and count the matches.
String word = "banana";
String out = "";
for (int i = 0; i < word.length(); i++)
{
String ch = word.substring(i, i + 1);
if (!ch.equals("a"))
{
out += ch;
}
}
System.out.println(out);- Abnn
- Baaa
- Cbnna
- Dnnb
Show the answer
A. The loop keeps every character that isn't "a": b (index 0), n (2) and n (4), giving "bnn". Choice B is the opposite test. Choice C keeps the last a, but every "a" fails the test, including the one at the end.
- Traverse with for (int i = 0; i < s.length(); i++) and s.substring(i, i + 1).
- Build new Strings from "", gluing with +. Glue on the front to reverse.
- A k-letter window: substring(i, i + k), with i <= s.length() - k.
- indexOf finds the first match or -1; "aeiou".indexOf(ch) == -1 tests "not a vowel".