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.
Start: Begin with a counter set to zero.
Visit each character: Traverse h, e, l, l, and o in order.
Update 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.
Finish: 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.
Identify the limitation: An individual character cannot be assigned a new value inside the existing string because strings are immutable.
Build a replacement: Combine parts of the original string with the desired new character, or use a string method that returns a new string.
Keep 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
Treating the first character as index 1.
Sequence indices begin at 0, so the first character is at index 0.
Fix:
Count positions from 0 and continue upward through the sequence.Including the stop index in a slice.
The start index is inclusive, but the end index is exclusive.
Fix:
Include indices 1, 2, and 3, and exclude index 4.Expecting a string character to change in place.
Strings are immutable.
Fix:
Create a new string through concatenation or a string method.Confusing traversal with search.
A search can stop when its target is found, while a full traversal visits every item.
Fix:
Stop at the first match when the task only requires locating a target.Treating an empty string as an error.
The empty string is a legitimate string containing no items.
Fix:
Handle 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.
- Use 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.