Introduction to Implementing String Algorithms
Welcome! In previous lessons, you learned how while and for loops work. Now, it's time to put those tools to work by manipulating text. String algorithms are a massive part of the AP Computer Science A exam—in fact, part of the Free-Response Section (Question 1, Part B) specifically requires you to call String methods to solve problems. Learning how to "walk through" a String character-by-character is a fundamental skill that every programmer needs.
The "Toolbox": Essential String Methods
Before we build algorithms, we need our tools. According to the AP Java Quick Reference, here are the methods you must know for this unit:
- \(int\) length(): Returns the number of characters in the string.
- \(String\) substring(\(int\) from, \(int\) to): Returns the text from index \(from\) to index \(to - 1\).
- \(String\) substring(\(int\) from): Returns the text from index \(from\) to the very end.
- \(int\) indexOf(\(String\) str): Returns the index of the first occurrence of \(str\), or \(-1\) if it’s not found.
- \(boolean\) equals(\(Object\) other): Returns \(true\) if two strings have the same characters.
- \(int\) compareTo(\(String\) other): Returns \(0\) if they are equal, a negative value if the string comes before \(other\) alphabetically, and a positive value if it comes after.
Quick Review: String indices start at \(0\) and end at \(length() - 1\). If you try to access an index equal to \(length()\), Java will throw an \(StringIndexOutOfBoundsException\)!
Algorithm 1: String Traversal
Traversal is just a fancy word for "visiting every part of something." To traverse a String, we use a for loop that starts at index \(0\) and stops just before the string's length.
The Standard "Character-by-Character" Loop
Since the AP CS A curriculum (Unit 1) focuses on the \(String\) type rather than the \(char\) type, we usually "grab" individual characters using \(substring(i, i + 1)\).
Example: Printing every character in a String \(s\)
for (\(int\) \(i = 0\); \(i < s.length()\); \(i++\))
{
\(String\) letter = \(s.substring(i, i + 1)\);
\(System.out.println(letter)\);
}
Did you know? In the loop header \(i < s.length()\), the loop runs for the last time when \(i\) is \(s.length() - 1\). This is perfect because that is the very last valid index!
Key Takeaway
To examine every single character, use a loop from \(0\) to \(length() - 1\) and extract a substring of length \(1\).
Algorithm 2: Counting Occurrences
A common task is counting how many times a specific letter or word appears in a String. To do this, we combine a for loop with an if statement and a counter variable.
The "Counting" Logic:
- Initialize an \(int\) counter to \(0\).
- Loop through the String.
- At each step, check if the current character matches your target.
- If it matches, increment the counter (\(count++\)).
Common Mistake: Using \(==\) to compare Strings. Remember, \(==\) checks if the memory addresses are the same. Always use .equals() to check if the content of the text is the same!
Algorithm 3: Building a New String
Strings in Java are immutable, which means they cannot be changed once created. If you want to "modify" a String (like reversing it or removing vowels), you must build a new String from scratch using concatenation.
Example: Reversing a String
To reverse a String, you can loop through the original String and always add the new character to the front of your result String.
The Logic:
\(String\) \(original\) = "apple";
\(String\) \(reversed\) = "";
for (\(int\) \(i = 0\); \(i < original.length()\); \(i++\))
{
\(reversed\) = \(original.substring(i, i + 1) + reversed\);
}
After the loop, \(reversed\) will be "elppa".
Key Takeaway
When creating a modified version of a String, start with an empty String (\( "" \)) and add to it inside your loop.
Algorithm 4: Substring Search (The "Sliding Window")
Sometimes you need to look for a word that is longer than one character. This is where you have to be very careful with your loop boundaries.
Suppose you want to count how many times the word "the" appears in a String. "the" has a length of \(3\). If you look for a substring of length \(3\) at the very end of your String, you might go "out of bounds."
The "Safe" Boundary Formula:
If you are looking for a substring of length \(n\), your loop should stop at \(i <= s.length() - n\).
Example: Finding "the" (length \(3\))
for (\(int\) \(i = 0\); \(i <= s.length() - 3\); \(i++\))
{
if (\(s.substring(i, i + 3).equals("the")\))
{
\(//\) Found one!
}
}
Don't worry if this seems tricky! Just remember: if your substring is length \(3\), and your string length is \(10\), the last index you can start at is \(7\). \(10 - 3 = 7\). This ensures indices \(7, 8, \text{ and } 9\) are checked, which are the last three characters.
Common Pitfalls to Avoid
- Off-by-one errors: Forgetting that \(substring(start, end)\) does not include the character at the \(end\) index.
- Case Sensitivity: "Apple" is not equal to "apple". If the problem asks you to count all 'A's, you might need to check for both uppercase and lowercase.
- Infinite Loops: Ensure your loop control variable (\(i\)) is actually moving toward the exit condition (\(i++\)).
Chapter Summary
To master String algorithms in Unit 2, focus on these three pillars:
- Traversing: Using a \(for\) loop to visit indices from \(0\) to \(length() - 1\).
- Extracting: Using \(substring(i, i + 1)\) to isolate characters.
- Comparing/Building: Using \(.equals()\) to check content and \(+\) to build new results.
Quick Review Tip: If a question asks you to find the first occurrence of something, you can often use \(indexOf()\) instead of writing a whole loop. If you need to count all occurrences, you must use a loop!