Searching and Pattern Matching in Strings
A sequence is an ordered set of values identified by integer indices starting at 0; strings are sequences of characters.
A String as an Ordered Sequence
When you search a string, you are not examining an unstructured collection of characters. You are working with a sequence: an ordered set of values identified by integer indices beginning at 0. Because strings are sequences of characters, every character has a position that can be used to retrieve or examine it.
An index identifies one item in a sequence. A string such as 'hello' contains five characters, arranged in order at indices 0 through 4. A slice selects a contiguous range of items rather than one item.
Following the Traversal
To traverse a string means to visit every item systematically. Movement proceeds through the sequence in order, from one character to the next. Traversal is useful when a task requires examining every character, counting occurrences, or applying a transformation to all items.
Counting a Repeated Character
Examine the string 'hello' and count how many times the character 'l' appears.
- 1Start
Begin with a counter set to zero.
- 2Visit each character
Traverse h, e, l, l, and o in order.
- 3Update the counter
The counter remains unchanged for h and e, increases for the first l, remains increased for the second l, and remains unchanged for o.
- 4Finish
After every character has been visited, the counter represents the number of occurrences.
The character 'l' appears two times.
Search as Early-Stopping Traversal
Search is a specialized form of traversal. The process moves through the string and compares each character, or a relevant substring, with the target pattern. Unlike a traversal that must inspect every item, a search can stop as soon as the target is found. This early stopping is the defining difference between the two patterns.
A flag is useful when the search needs to remember whether a target was found. A counter is useful when the task asks how many matches occur. These supporting variables give the traversal a memory of what it has discovered so far.
Names, Methods, and Results
Strings provide methods for common operations, including converting a string to uppercase, finding the position of a character, and replacing one substring with another. A method is invoked by writing the string object or a variable holding it, then a dot, then the method name followed by parentheses. The dot connects the operation to the specific string object on which it should run.
Dot notation does not describe a separate string. It identifies the object that supplies the method. The method then performs its operation according to the method's purpose. When an operation creates a changed version of a string, that version is a new string rather than an in-place alteration of the original.
Immutability and New Strings
Strings are immutable. This means an individual character cannot be changed in place. Immutability does not prevent string processing; it means that an operation that appears to modify a string must instead create a new string. Concatenation and string methods can produce new strings while leaving the original string unchanged.
Changing a String Safely
Create a version of a string with a different character without changing the original string in place.
- 1Identify the limitation
An individual character cannot be assigned a new value inside the existing string because strings are immutable.
- 2Build a replacement
Combine parts of the original string with the desired new character, or use a string method that returns a new string.
- 3Keep both values conceptually distinct
The original string remains unchanged, while the operation produces a separate modified string.
String processing changes the value by creating a new string, not by altering an individual character in place.
Empty Strings and Boundaries
The empty string is a valid string value. It has length 0 and contains no items. It can occur when a user provides no input or when a search produces no matching text. Treating it as a legitimate value helps you distinguish an empty result from an error or an undefined state.
Mistakes in String Reasoning
Common mistake Treating the first character as index 1.
What it looks likeAssuming the first character of a string has index 1.
Why it failsSequence indices begin at 0, so the first character is at index 0.
Do this insteadCount positions from 0 and continue upward through the sequence.
Common mistake Including the stop index in a slice.
What it looks likeAssuming a slice from index 1 to index 4 includes the character at index 4.
Why it failsThe start index is inclusive, but the end index is exclusive.
Do this insteadInclude indices 1, 2, and 3, and exclude index 4.
Common mistake Expecting a string character to change in place.
What it looks likeTrying to assign a new character to one specific position in an existing string.
Why it failsStrings are immutable.
Do this insteadCreate a new string through concatenation or a string method.
Common mistake Confusing traversal with search.
What it looks likeContinuing to inspect every character after the target has already been found.
Why it failsA search can stop when its target is found, while a full traversal visits every item.
Do this insteadStop at the first match when the task only requires locating a target.
Common mistake Treating an empty string as an error.
What it looks likeAssuming a zero-length search result is not a valid value.
Why it failsThe empty string is a legitimate string containing no items.
Do this insteadHandle the empty string as a valid result or input.
Practice the Pattern
For the string 'hello', describe how you would solve each task: identify the character at index 2, select the slice from index 1 to index 4, traverse the entire string to count the character 'l', and search for the first occurrence of 'e'. State whether each task needs an index, a slice, a full traversal, or an early-stopping search.
Hints
- An index selects one item, while a slice selects a range.
- Counting occurrences requires examining every relevant character.
- A search may stop as soon as its target is found.
- 1Use the structure of the task to choose the operation: use an index for one character, a slice for a contiguous range, traversal for systematic examination of every character, and search for traversal that can stop when a target is found.
Key Takeaways
- Strings are sequences of characters arranged at integer indices beginning at 0.
- An index selects one item, while a slice selects a contiguous range with an inclusive start and exclusive end.
- Traversal visits sequence items systematically; search is traversal that can stop when a target is found.
- Strings are immutable, so changed versions are created rather than individual characters being altered in place.
- Counters and flags help traversal and search remember counts and whether a target was found.