7.9. Comparing StringsComparing strings is another important task. For example, when a word processor performs a search and replace operation, it needs to identify strings in the text that match the target string. Strings are compared according to their lexicographic orderthat is, the order of their characters. For the letters of the alphabet, lexicographic order just means alphabetical order. Thus, a comes before b, and d comes after c. The string "hello" comes before "jello" because h comes before j in the alphabet. For Java and other programming languages, the definition of lexicographic order is extended to cover all the characters that make up the character set. We know, for example, that in Java's Unicode character set, the uppercase letters come before the lowercase letters (Table 5.13). So the letter H comes before the letter h, and the letter Z comes before the letter a.
H precedes h Lexicographic order can be extended to include strings of characters. Thus, "Hello" precedes "hello" in lexicographic order because its first letter, H, precedes the first letter, h, in "hello". Similarly, the string "Zero" comes before "aardvark", because Z comes before a. To determine lexicographic order for strings, we must perform a character-by-character comparison, starting at the first character and proceeding left to right. As an example, the following strings are arranged in lexicographic order: "" "!" "0" "A" "Andy" "Z" "Zero" "a" "an" "and" "andy" "candy" "zero" We can define lexicographic order for strings as follows: Java Language Rule: Lexicographic Order
Perhaps a more precise way to define lexicographic order is to define a Java method: public boolean precedes(String s1, String s2) { // Pick shorter length int minlen = Math.min(s1.length(), s2.length()); for (int k=0; k < minlen; k++) { // For each char in shorter string if (s1.charAt(k) != s2.charAt(k)) // If chars unequal return s1.charAt(k) < s2.charAt(k);// return true if s1's char precedes s2's } return s1.length() < s2.length(); // If all characters so far are equal // then s1 < s2 if it is shorter than s2 } // precedes() This method does a character-by-character comparison of the two strings, proceeding left to right, starting at the first character in both strings. Its for loop uses a counting bound, which starts at k equal to zero and counts up to the length of the shorter string. This is an important point in designing this algorithm. If you don't stop iterating when you get past the last character in a string, your program will generate a StringIndexOutOfBounds exception. To prevent this error, we need to use the shorter length as the loop bound.
Algorithm: Loop bound Note that the loop will terminate early if it finds that the respective characters from s1 and s2 are unequal. In that case, s1 precedes s2 if s1's kth character precedes s2's. If the loop terminates normally, that means that all the characters compared were equal. In that case, the shorter string precedes the longer. For example, if the two strings were "alpha" and "alphabet", then the method would return true, because "alpha" is shorter than "alphabet". Self-Study Exercises
7.9.1. Object Identity versus Object EqualityJava provides several methods for comparing Strings: public boolean equals(Object anObject); // Overrides Object.equals() public boolean equalsIgnoreCase(String anotherString); public int compareTo(String anotherString); The first comparison method, equals(), overrides the Object.equals() method. Two Strings are equal if they have the exact same letters in the exact same order. Thus, for the following declarations,
Equality vs. identity String s1 = "hello"; String s2 = "Hello"; s1.equals(s2) is false, but s1.equals("hello") is true. You have to be careful when using Java's equals() method. According to the default definition of equals(), defined in the Object class, "equals" means "identical." Two Objects are equal only if their names are references to the same object. This is like the old story of the morning star and the evening star, which were thought to be different objects before it was discovered that both were just the planet Venus. After the discovery, it was clear that "the morning star" and "the evening star" and "Venus" were just three different references to one and the same object (Fig. 7.12). Figure 7.12. Venus is the morning star, so "Venus" and "the morning star" are two references to the same object.
We can create an analogous situation in Java by using the following JButton definitions: JButton b1 = new Button("a"); JButton b2 = new Button("a"); JButton b3 = b2; Given these three declarations, b1.equals(b2) and b1.equals(b3) would be false, but b2.equals(b3) would be true because b2 and b3 are just two names for the same object (Fig. 7.13). So in this case "equals" really means "identical." Figure 7.13. For most objects, equality means identity. JButtons b2 and b3 are identical (and hence equal), but JButtons b1 and b2 are not identical (and hence unequal). |
import java.awt.*; public class TestEquals { static Button b1 = new Button ("a"); static Button b2 = new Button ("b"); static Button b3 = b2; private static void isEqual(Object o1, Object o2) { if (o1.equals(o2)) System.out.println(o1.toString() + " equals " + o2.toString()); else System.out.println(o1.toString() + " does NOT equal " + o2.toString()); } // isEqual() private static void isIdentical(Object o1, Object o2) { if (o1 == o2) System.out.println(o1.toString() + " is identical to " + o2.toString()); else System.out.println(o1.toString() + " is NOT identical to " + o2.toString()); } // isIdentical() public static void main(String argv[]) { isEqual(b1, b2); // not equal isEqual(b1, b3); // not equal isEqual(b2, b3); // equal isIdentical(b1, b2); // not identical isIdentical(b1, b3); // not identical isIdentical(b2, b3); // identical } // main() } // TestEquals class |
In comparing Java Strings, we must be careful to distinguish between object identity and string equality. Thus, consider the following declarations, which create the situation shown in Figure 7.15.
String s1 = new String("hello"); String s2 = new String("hello"); String s3 = new String("Hello"); String s4 = s1; // s1 and s4 are now identical String s5 = "hello"; String s6 = "hello";
Given these declarations, we would get the following results if we compare the equality of the Strings:
s1.equals(s2) ==> true s1.equalsIgnoreCase(s3) ==> true s1.equals(s3) ==> false s1.equals(s5) ==> true s1.equals(s4) ==> true s1.equals(s6) ==> true
Equality vs. identity
and the following results if we compare their identity:
s1 == s2 ==> false s1 == s3 ==> false s1 == s4 ==> true s1 == s5 ==> false s5 == s6 ==> true
The only true identities among these Strings are s1 and s4, and s5 and s6. In the case of s5 and s6, both are just references to the literal string "hello", as we described in Section 7.2. The program in Figure 7.16 illustrates these points.
import java.awt.*; public class TestStringEquals { static String s1 = new String("hello"); // s1 and s2 are equal, not identical static String s2 = new String("hello"); static String s3 = new String("Hello"); // s1 and s3 are not equal static String s4 = s1; // s1 and s4 are identical static String s5 = "hello"; // s1 and s5 are not identical static String s6 = "hello"; // s5 and s6 are identical private static void testEqual(String str1, String str2) { if (str1.equals(str2)) System.out.println(str1 + " equals " + str2); else System.out.println(str1 + " does not equal " + str2); } // testEqual() private static void testIdentical(String str1, String str2) { if (str1 == str2) System.out.println(str1 + " is identical to " + str2); else System.out.println(str1 + " is not identical to " + str2); } // testIdentical() public static void main(String argv[]) { testEqual(s1, s2); // equal testEqual(s1, s3); // not equal testEqual(s1, s4); // equal testEqual(s1, s5); // equal testEqual(s5, s6); // equal testIdentical(s1, s2); // not identical testIdentical(s1, s3); // not identical testIdentical(s1, s4); // identical testIdentical(s1, s5); // not identical testIdentical(s5, s6); // identical } // main() } // TestStringEquals class ------Program Output----- hello equals hello hello does not equal Hello hello equals hello hello equals hello hello equals hello hello is not identical to hello hello is not identical to Hello hello is identical to hello hello is not identical to hello hello is identical to hello |
Exercise 7.16 | Given the String declarations, String s1 = "java", s2 = "java", s3 = "Java"; String s4 = new String(s2); String s5 = new String("java"); evaluate the following expressions:
|
Exercise 7.17 | Why are the variables in TestStringEquals declared static? |
Exercise 7.18 | Given the following declarations, String s1 = "abcdefghijklmnopqrstuvwxyz"; String s2 = "hello world"; write Java expressions to carry out each of the following operations:
|