1.15 String Manipulation

1.15 String Manipulation

A string is a sequence of characters whose positions begin at index $0$, so finding a word inside another string is an exercise in locating boundaries precisely. For example, in "caterpillar", the target "cat" begins at index $0$, has length $3$, and can be removed with substring(3).

Prefix matching: finding and removing a target

The indexOf method returns the index at which a target string first appears, or $-1$ when the target does not appear. Therefore, the test

current.indexOf(target) == 0

means specifically that target occurs at the beginning of current. It does not merely mean that the target appears somewhere.

Once a prefix match is confirmed, substring(target.length()) returns everything after that prefix. The starting index is inclusive, and the ending index is implicitly the end of the string.

String current = "catapult";
String target = "cat";

if (current.indexOf(target) == 0) {
    String remainder = current.substring(target.length());
    System.out.println(remainder);   // "apult"
}

The target is not removed from the original object; Java String objects are immutable, meaning their character sequences cannot be changed in place. substring creates the desired result, which must be stored in a variable or added to another collection.

Three locations that must not be confused

A target can have a no-match, match-start, match-end, interior, or whole-string relationship with the current string. String algorithms should distinguish the required cases explicitly rather than treating every non-prefix match as equivalent.

Case	Example: current and target	Reliable test
No match	"blue", "red"	current.indexOf(target) == -1
Match-start	"catapult", "cat"	current.indexOf(target) == 0
Match-end	"tomcat", "cat"	current.endsWith(target)
Interior match	"educate", "cat"	Match exists but is neither at index $0$ nor at the ending index
Entire string	"cat", "cat"	current.equals(target)

For a nonempty target, match-end can also be expressed numerically:

current.indexOf(target) == current.length() - target.length()

For "tomcat", the first index of "cat" is $3$, while current.length() - target.length() is $6 - 3 = 3$. This differs from a match-start, whose index is $0$. When the target occupies the entire string, both boundary calculations produce $0$; equals makes that whole-string case unambiguous.

Traversing a word list without changing it

Suppose wordList contains no null elements and must remain unchanged. A traversal can inspect each current string and, when necessary, compare it with the previous string. The loop begins at index $1$ when the algorithm needs a previous element, because index $0$ has no predecessor.

public boolean isWordChain() {
    String previous = wordList.get(0);

    for (int i = 1; i < wordList.size(); i++) {
        String current = wordList.get(i);

        if (current.indexOf(previous) == -1) {
            return false;
        }

        previous = current;
    }

    return true;
}

Here, previous stores the string that the next current must contain. The algorithm returns false immediately when one link fails; if every link succeeds, it returns true. The list itself is only read through get, so its contents and order are preserved.

Building a separate result list

A transformation problem should usually create a new ArrayList<String> rather than replacing elements in wordList. The following method adds the portion remaining after a matching prefix and ignores strings with no prefix match.

public ArrayList<String> createList(String target) {
    ArrayList<String> result = new ArrayList<String>();
    int targetLength = target.length();

    for (int i = 0; i < wordList.size(); i++) {
        String current = wordList.get(i);

        if (current.indexOf(target) == 0) {
            result.add(current.substring(targetLength));
        }
    }

    return result;
}

For wordList = ["preheat", "heat", "preview"] and target = "pre", the result becomes ["heat", "view"]; the original list remains ["preheat", "heat", "preview"]. "heat" is a no-match and is handled separately by simply not being added.

Misconception check

Misconception: “If indexOf(target) is not $-1$, the target is a prefix.” False. A return value of $0$ means prefix; a positive value may indicate an interior or match-end occurrence. Also, substring(target.length()) is correct only after confirming a prefix match—otherwise it removes characters from the beginning even when the target was absent or located elsewhere.

Retrieval check

Given current = "notebook" and target = "book", identify the case and the correct condition. The target is a match-end: current.endsWith(target) is true, and current.indexOf(target) == current.length() - target.length() is also true. It is not a match-start because its index is $4$, not $0$.