Beyond what we can do with the String methods we looked at in the previous section, there are a number of algorithms for manipulating and producing String values, often by treating a String as a collection of individual characters that we loop over. Some of them are somewhat similar to array algorithms we covered in Chapter 6 Arrays. Others are a bit different because, unlike arrays, String values are immutable so we can produce new String values based on existing values but we can’t change a String once it is created.
The first category of String algorithms are related to the array searching algorithms we discussed in Subsection 6.3.3 Searching and the the any and all algorithms from Subsection 6.3.4 Any and all. However rather than searching for or testing elements of an array, we will search for or test for the presence of substrings of a given string that have certain properties. The basic structure of this sort of algorithm is a canonical for loop that loops over the valid indices of the String and calls to the substring method inside the loop to extract substrings that we can then test to see if they have whatever property we care about. As a really simple example of this we can test whether any single character, a.k.a. a one-character substring, in the Strings is a lowercase vowel with this code:
public boolean containsVowel(String s) {
for (int i = 0; i < s.length(); i++) {
if ("aeiou".indexOf(s.substring(i, i + 1)) != -1) {
return true;
}
}
return false;
}
Notice that the loop is just a canonical for loop over the valid indices of s. All the interesting work happens inside the loop. In the if inside the loop we use the expression s.substring(i, i + 1) to extract the one-character substring starting an index i. Then we check if it’s a vowel by testing whether it occurs somewhere in the string "aeiou", using the fact that indexOf returns -1 if the argument is not present in the StringindexOf was called on.
That is the basic pattern. We could have used the same pattern but returned the substring we found. Or we could have looped through the whole string and kept a count of how many vowels we saw. Or tested every substring and returned false if any of them weren’t vowels to implement a method to check whether every every letter of the String was a vowel.
That is, with a for loop and a call to substring to extract the subtring, we can build any of the finding, counting, and property testing algorithms we first used with arrays.
The following main method has the correct code to count the number of e’s in a string, but the code is mixed up. Drag the blocks from the left area into the correct order in the right area. Click on the “Check Me” button to check your solution.
public static void main(String[] args)
{
---
String message = "e is the most frequent English letter.";
int count = 0;
---
for(int i=0; i < message.length(); i++)
{
---
if (message.substring(i,i+1).equalsIgnoreCase("e"))
---
count++;
---
}
---
System.out.println(count);
---
}
Since String values are immutable it might seem that we can’t remove anything from a String. But we can in the same sense that we can subtract one number from another and get a new number. That is, we can make a new String that is made up of parts of the original String with some parts left out.
To take a really simple example, suppose we wanted to remove the substring "cd" from "abcdef" to get "abef". Since both values are fixed we can just count letters and see that substring we want to remove starts at index 2 and ends at index 4 as shown in the diagram below.
But in order to remove the "cd" we want to get the two substrings before and after it: the one from the start up to position 2 and the one starting at position 4 to the end of the string. The following code demonstrates how to use substring and + to extract those two parts and concatenate them to get the string with "cd" removed.
String s = "abcdef";
System.out.println(s.substring(0, 2) + s.substring(4)); // prints "abef"
Now to make things slightly more interesting, suppose we want to take the specific substring "and cheese " out of some String that contains it, perhaps something like "Ham and cheese sandwich". This code does that:
String sandwich = "Ham and cheese sandwich."; // Could be anything that contains "and cheese "
int start = sandwich.indexOf("and cheese "); // Figure out where it starts ...
int end = start + "and cheese ".length(); // And where it ends
sandwich = sandwich.substring(0, start) + sandwich.substring(end);
In this code we got the computer to figure out what indices we needed to use by finding the start af the substring we want to snip out with indexOf and then adding the length of the substring to that to get the end.
Notice also how the last lines assigns the new value back to the variable sandwich. While that doesn’t change the original String—assigning to a variable never has an effect on the value previously stored in that variable—it does mean that after that line the value of sandwich no longer contains "and cheese ".
Now we are ready to see an algorithm for computing a string with all the occurrences of a particular substring removed. We just need to wrap the previous code in a while loop that runs as long as the String we want to remove is still present in the String referenced by the variable.
We use a while loop because we don’t need a loop variable and also we don’t know how many times the loop needs to run; we just want to keep running as long as there’s still at least once occurrence of the string to be removed.
This code shows a method that computes a new String value consisting of the text of its first argument with all occurrences of its second argument removed:
The following program removes all the a’s from a string, but the code is mixed up. Drag the blocks from the left area into the correct order in the right area. Click on the “Check Me” button to check your solution.
public static void main(String[] args)
{
---
String s = "are apples tasty without an a?";
int index = 0;
System.out.println("Original string: " + s);
---
// while there is an a in s
while (s.indexOf("a") >= 0)
{
---
// Find the next index for an a
index = s.indexOf("a");
---
// Remove the a at index by concatenating
// substring up to index and then rest of the string.
s = s.substring(0,index) +
s.substring(index+1);
---
} // end loop
---
System.out.println("String with a's removed:" + s);
---
} // end method
Google has been scanning old books and then using software to read the scanned text. But, the software can get things mixed up like using the number 1 for the letter l. Try the code below (and in the Java visualizer) to clean up scanning mistakes like this.
The following code loops through a string replacing all 1’s with l’s. Trace through the code below with a partner and explain how it works on the given message. You can run it line by line in the Java visualizer. Note that indexOf here can work repeatedly to find the next occurrence of a 1 because they are replaced as soon as they are found.
Change the code to add code for a counter variable to count the number of 1’s replaced in the message and print it out. Change the message to have more mistakes with 1’s to test it.
Finally, let’s look at how to reverse a String. The algorithm for reversing a String is a bit different from the algorithm for reversing an array we discussed in Subsection 6.3.7 Reversing an array since we can’t swap the characters in a Sting in place because a String is immutable. So we have to produce a new String whose contents are the original String but in reverse order.
We can use a similar strategy as in the previous algorithm, but this time instead of assigning new values to a variable that contain only parts of the current value, we’ll build up a String one character at a time.
Since we’re going to need to do something with each character of the String, a for loop is an appropriate choice. To keep things simple we can use a canonical for loop, processing each character in order and then reverse it by how we build up the new String.
Here is a for loop that creates a new String that contains the contents of s but in reverse. We start with a blank string reversed and build up our reversed string in that variable by copying each character from the Strings in order but putting each new character at the front of the String we are building up. Clearly that puts the original first character last and the last character first.
What would happen if you started the loop at 1 instead? What would happen if you used <= instead of <? What would happen if you changed the order in which you added the letter at line 8?
Write some code below that changes every occurrence of "cat" to "dog" in the message. This code will be more like the first program in this lesson where we replaced 1’s with l’s.
(Optional - challenging and not autograded) What if you like both cats and dogs? After you replace "cat" with "dog", add another loop that looks for the word "dogs" and adds " and cats" to it. Do not replace "dog", just "dogs". This will only change the first sentence in the example below but you can add other sentences to test.
For this loop, you will need to use a special version of indexOf that takes two arguments where the second argument is the index to start looking from, rather than starting at index 0. If you don’t use this version you’ll probabyl end up with an infinite loop endlessly finding the first occurrence of "dogs". Make sure you add a variable fromIndex that is initialized to 0 and that is changed each time through the loop to skip over the last word that was found.
The two-argument version of int indexOf(String target, int fromIndex) searches left-to-right for the target substring, but starts the search at the given fromIndex. You are not required to know this version of indexOf for the AP CSA exam, but you can use it (and any valid Java code) in the Free Response Questions.
