TOPIC 2.10 · STUDY

Implementing String Algorithms

String algorithms walk indexes from 0 through length() - 1. substring(from, to) keeps from and stops before to; substring(from) runs to the end. Strings are immutable, so a lone substring call leaves the original unchanged. Loops can inspect one character with substring(i, i + 1) or charAt(i), compare pieces with equals, find starts with indexOf, reverse text, or scan overlapping windows.

2.10.A

Implementing String algorithms

Topic 2.10 builds small algorithms on String indexes and methods. Characters are numbered from 0. For a string of length n, valid indexes run from 0 through n - 1. length() returns n. Algorithms that visit every character usually loop while the index stays strictly less than length().

substring(from, to) returns a new String made of the characters from index from through index to - 1. It includes from and excludes to. The one-argument form substring(from) keeps every character from that index through the end of the string.

The word ember with index numbers 0 through 4 under each letter. Boxes for indexes 1, 2, and 3 are highlighted to show substring(1, 4) selecting mbe.

Indexes start at 0. substring(1, 4) keeps characters at 1, 2, and 3 and stops before 4.

String ember = "ember";
System.out.print(ember.substring(1, 4));
System.out.print("," + ember.substring(2));
System.out.print("," + ember.length());

That sequence prints mbe,ber,5. substring(1, 4) keeps m, b, and e. substring(2) keeps ber through the end. length() still reports 5 for the full original string.

A String is immutable. Calling a method such as substring builds a different String; the characters inside the original object do not change. A variable updates only when the program assigns the new result back to it.

String tag = "coral";
System.out.print(tag.substring(2));
System.out.print(tag.length());

tag = tag.substring(2);
System.out.print("," + tag + tag.length());

The first prints are ral and then 5, because tag still refers to "coral". After the assignment, tag refers to "ral", so the next print is ral3.

A loop from 0 to length() - 1 can inspect one character at a time. substring(i, i + 1) returns a one-character String. charAt(i) returns that character as a char. Both stay in range when i runs from 0 while i < length().

String mist = "moss";
int hits = 0;
for (int i = 0; i < mist.length(); i++) {
    if (mist.substring(i, i + 1).equals("s")) {
        hits++;
    }
}
System.out.print(hits);

Indexes 0 through 3 visit m, o, s, s. equals compares the one-character piece with "s", so hits becomes 2. The same count works with if (mist.charAt(i) == 's').

indexOf returns the first starting index of a match, or -1 when the target is absent. Algorithms often store that index and then take a substring from there, or use indexOf on a short catalog string to test membership of one character.

String path = "meadow";
int at = path.indexOf("do");
System.out.print(at);
System.out.print("," + path.substring(at));

int vowels = 0;
for (int i = 0; i < path.length(); i++) {
    String ch = path.substring(i, i + 1);
    if ("aeiou".indexOf(ch) >= 0) {
        vowels++;
    }
}
System.out.print("," + vowels);

In meadow, do begins at index 3, so the first prints are 3 and dow. The vowel loop finds e, a, and o, so vowels is 3.

Reversing a string walks indexes from length() - 1 down to 0 and concatenates each character into a new String. Prefix and suffix checks clip with substring, then compare the clip with equals.

String tide = "tide";
String rev = "";
for (int i = tide.length() - 1; i >= 0; i--) {
    rev += tide.substring(i, i + 1);
}
System.out.print(rev);

if (tide.substring(0, 2).equals("ti")) {
    System.out.print(",yes");
}

The reverse loop stores edit. substring(0, 2) is ti, which equals the literal, so yes is appended.

Overlapping windows slide a fixed-length substring across the text. For length-2 windows, the last legal starting index is length() - 2. Adjacent starts share a character, so matches can sit next to each other.

String buzz = "zzzz";
int pairs = 0;
for (int i = 0; i <= buzz.length() - 2; i++) {
    if (buzz.substring(i, i + 2).equals("zz")) {
        pairs++;
    }
}
System.out.print(pairs);

Starting indexes 0, 1, and 2 each see zz, so pairs is 3.

Key points

  • Character indexes start at 0; length() is the character count.
  • substring(from, to) includes from and excludes to; substring(from) runs through the end.
  • A String is immutable; substring does not change the original unless you assign the result.
  • A loop from 0 while i < length() can inspect one character with substring(i, i + 1) or charAt(i).
  • equals compares contents; indexOf returns the first match index or -1.
  • Reverse by walking from length() - 1 down to 0; scan length-k windows up to length() - k.

Calling substring does not change the original string unless you assign the result.

Practice this topic