Skip to main content

ITSC 1213 - Introduction to CS 2 How to Design Programs with Object Oriented Programming

Nadia Najjar, Dhruv Dhamani

Section 5.4 Searching in Strings

Subsection 5.4.1 Step 0: Understanding & Restating the Problem

In many real-world programs, we need to search strings. For instance:
  • A chat application might check if a user typed a special command like @everyone.
    🔗
  • A text-based game might parse "take sword" to detect the verb "take" and the object "sword".
    🔗
Searching is how we detect these features in user input.
🔗
Formally, the problem is: "Given a string, find whether a certain substring is present and, if so, at which index." We’ll apply the Design Recipe steps—especially Step 3 (Examples & Tests)—to handle typical search tasks systematically.
🔗
🔗

Subsection 5.4.2 Step 1: Recap Data Definition for MyString

Recall that our MyString class has:
🔗
  • A char[] chars of fixed length 100 (a simple capacity constraint).
    🔗
  • An int usedLength tracking how many characters are actually used (0..100).
    🔗
We limit ourselves to 100 characters to keep the design manageable—real Java strings have no such limit, but this approach helps illustrate fundamentals without worrying about resizing arrays or throwing exceptions.
🔗
Thus, conceptually, a MyString is the sequence chars[0..usedLength-1]. Next, we define the methods we’ll write (Step 2) before enumerating tests (Step 3) and coding (Steps 4 and 5).
🔗
🔗

Subsection 5.4.3 Step 2: Method Signatures & Purpose

In Java, you’d find similar methods in String (indexOf, lastIndexOf, contains). We’ll create analogous methods in our MyString class.
🔗
Simplified Error Policy: Throughout these methods, we take a simplified approach to errors:
  • We treat null targets as empty strings ("") rather than throwing NullPointerException
    🔗
  • We return -1 for impossible matches (like targets longer than the string) rather than throwing exceptions
    🔗
  • We use print-based testing rather than JUnit or assert statements to keep focus on the core logic
    🔗
This differs from real Java’s String class (which throws exceptions), but simplifies learning.
🔗
🔗

Subsection 5.4.4 Step 3: Examples & Tests

Before coding, we list normal and edge scenarios in test tables. It’s crucial to test each case immediately after implementing or modifying a method—don’t wait until the end! Feel free to add rows if you discover new edge conditions later—this iterative mindset is central to the Design Recipe.
🔗

Subsubsection 5.4.4.1 indexOf(String target) Test Table

Table 5.4.1. Test Cases for indexOf
🔗
Case MyString Target Expected
Found in middle "banana" "ana" 1
Found at start "banana" "ban" 0
Overlapping matches "aaaa" "aaa" 0
Repeated ⟹ 1st match "aaaa" "aa" 0
Empty target ⟹ 0 "banana" "" 0
Not found "banana" "cat" -1
Longer ⟹ -1 "cat" "cater" -1
Empty MyString ⟹ -1 "" "xyz" -1
Both empty ⟹ 0 "" "" 0
Null target ⟹ 0 "banana" null 0
This covers typical usage ("ana" in "banana") plus special cases (empty substring, overlapping matches, null handling, etc.).
🔗
🔗

Subsubsection 5.4.4.2 lastIndexOf(String target) Test Table

Table 5.4.2. Test Cases for lastIndexOf
🔗
Case MyString Target Expected
Found at end "banana" "ana" 3
Overlapping matches "aaaa" "aaa" 1
Repeated => last occurrence "aaaa" "aa" 2
Not found "banana" "xyz" -1
Empty target => usedLength "banana" "" 6
Null target => usedLength "banana" null 6
If target is "" or null, we return usedLength (6 for "banana"), aligning with real Java’s behavior for empty strings.
🔗
🔗

Subsubsection 5.4.4.3 contains(String target) Test Table

Table 5.4.3. Test Cases for contains
🔗
Case MyString Target Expected
Found "banana" "ana" true
Not found "banana" "xyz" false
Empty target "banana" "" true
Both empty "" "" true
Null target "banana" null true
Since contains checks if indexOf is not -1, it inherits the same error handling behavior.
🔗
🔗
🔗

Subsection 5.4.5 Step 4: Skeleton for Our Search Methods

Next, we outline each method in pseudocode. That way we confirm loops and logic before coding. You can sketch this on paper or in comments:
🔗
public int indexOf(String target) {
    // if target == null, treat as ""
    // if target == "", return 0
    // if target.length() > usedLength, return -1
    // loop over possible starts
    //    compare chars[i..i+target.length()-1] with target
    //    if match => return i
    // return -1
}

public int lastIndexOf(String target) {
    // if target == null, treat as ""
    // if target == "", return usedLength
    // if target.length() > usedLength => -1
    // loop backward from usedLength - target.length() down to 0
    //    compare substring
    //    if match => return start
    // return -1
}

public boolean contains(String target) {
    // return (indexOf(target) != -1)
}
This skeleton ensures we know the structure before writing final code.
🔗
🔗

Subsection 5.4.6 Step 5: Implementation, Testing & Refinement

We’ll now fill in each method. After writing each method, we immediately test it against the rows in the tables above. This "code a bit, test a bit" approach catches errors early—a core habit we want to instill. When tests fail or produce unexpected results, we’ll refine our approach by revisiting earlier steps.
🔗

Subsubsection 5.4.6.1 Implementing indexOf 

public int indexOf(String target) {
    // treat null as "" to avoid errors
    if (target == null) {
        target = "";
    }
    // empty => 0
    if (target.equals("")) {
        return 0;
    }
    // too long => -1
    if (target.length() > usedLength) {
        return -1;
    }
    // search
    for (int start = 0; start <= usedLength - target.length(); start++) {
        boolean match = true;
        for (int j = 0; j < target.length(); j++) {
            if (chars[start + j] != target.charAt(j)) {
                match = false;
                break;
            }
        }
        if (match) {
            return start;
        }
    }
    // not found
    return -1;
}
After writing this, test each case from the table using our helper method. If any test fails, we’ll need to refine our implementation or update our test assumptions:
🔗
private static void testResult(String desc, Object actual, Object expected) {
    System.out.print(desc + " => " + actual);
    if (actual.equals(expected)) {
        System.out.println(" PASS");
    } else {
        System.out.println(" FAIL (expected " + expected + ")");
        // When a test fails, consider:
        // 1. Is the implementation wrong?
        // 2. Is the test case's expected value wrong?
        // 3. Did we discover a new edge case?
    }
}

// In main:
MyString fruit = new MyString("banana");
testResult("indexOf('ana')", fruit.indexOf("ana"), 1);
testResult("indexOf('cat')", fruit.indexOf("cat"), -1);
testResult("indexOf('')", fruit.indexOf(""), 0);
testResult("indexOf(null)", fruit.indexOf(null), 0);
For example, if indexOf unexpectedly fails for an overlapping substring, revisit your skeleton (Step 4) or test cases (Step 3) and update them to reflect the actual behavior or fix the implementation.
🔗
🔗

Subsubsection 5.4.6.2 Implementing lastIndexOf 

public int lastIndexOf(String target) {
    if (target == null) {
        target = "";
    }
    // empty => usedLength
    if (target.equals("")) {
        return usedLength;
    }
    if (target.length() > usedLength) {
        return -1;
    }
    // search backward
    for (int start = usedLength - target.length(); start >= 0; start--) {
        boolean match = true;
        for (int j = 0; j < target.length(); j++) {
            if (chars[start + j] != target.charAt(j)) {
                match = false;
                break;
            }
        }
        if (match) {
            return start;
        }
    }
    return -1;
}
Test each case, including overlapping matches. Document any refinements needed:
🔗
// Implementation Notes:
// 1. Changes from original design:
//    - Updated empty string behavior to return usedLength instead of 0
// 2. Additional edge cases found:
//    - Overlapping pattern "aaa" in "aaaa" needs careful bounds
// 3. Optimization opportunities:
//    - Could cache indexOf results for contains()

testResult("lastIndexOf('ana')", fruit.lastIndexOf("ana"), 3);
testResult("lastIndexOf('xyz')", fruit.lastIndexOf("xyz"), -1);
testResult("lastIndexOf('')", fruit.lastIndexOf(""), 6);

MyString repeated = new MyString("aaaa");
testResult("lastIndexOf('aaa') in 'aaaa'", repeated.lastIndexOf("aaa"), 1);
testResult("lastIndexOf('aa') in 'aaaa'", repeated.lastIndexOf("aa"), 2);
🔗

Subsubsection 5.4.6.3 Implementing contains 

public boolean contains(String target) {
    return (indexOf(target) != -1);
}
Test all cases, including null handling. Note any refinements needed:
🔗
// Implementation Notes:
// 1. Reuse of indexOf simplifies testing
// 2. Verified inheritance of null/empty handling

testResult("contains('ana')", fruit.contains("ana"), true);
testResult("contains('xyz')", fruit.contains("xyz"), false);
testResult("contains('')", fruit.contains(""), true);
testResult("contains(null)", fruit.contains(null), true);
If any test fails, revisit the method’s logic or update test expectations. Document any changes in implementation notes.
🔗
🔗
Remember: whenever tests fail or produce unexpected results, revisit the skeleton (Step 4) or the test tables (Step 3) to refine assumptions, logic, or data definitions. This ’Refinement’ loop ensures your final code truly reflects all discovered requirements.
🔗
🔗

Subsection 5.4.7 The Complete MyString (With Searching)

Below is a single, runnable version of MyString that you can copy into a file (e.g. MyString.java), compile, and run. It includes the constructor, data initialization, our three new search methods, and a test helper method that prints PASS/FAIL for each case.
🔗
Run this code and verify all tests pass. Pay special attention to overlapping matches (like "aaa" in "aaaa") and edge cases (empty strings, null). If you find additional cases to test, add them to both the test tables and the main method, documenting any refinements made during implementation.
🔗
🔗

Subsection 5.4.8 Step 6: Reflection & Conclusion

By enumerating test cases (Step 3) before coding, we preempted many pitfalls—especially with:
  • Empty strings and null targets (treating them consistently)
    🔗
  • Overlapping matches (like "aaa" in "aaaa")
    🔗
  • "Not found" scenarios returning -1
    🔗
  • Matching Java’s behavior where practical (e.g., lastIndexOf("") returns usedLength)
    🔗
🔗
We encourage you to:
  • Use the testResult helper to verify each test case passes
    🔗
  • Add more test cases if you discover new edge conditions
    🔗
  • Compare behavior with real Java’s String methods to understand any differences
    🔗
  • Consider how you might handle errors differently (e.g., with exceptions) in production code
    🔗
  • Document any refinements made during implementation in the Implementation Notes section
    🔗
🔗
This completes our demonstration of searching in MyString using Steps 0–6. In the next section, we’ll move on to more advanced string operations, but remember: the same Design Recipe steps apply—just start by stating your method’s purpose, enumerating examples, and verifying behavior thoroughly!
🔗
🔗

Subsection 5.4.9 Check Your Understanding

Exercises Exercises

1. Multiple-Choice: indexOf(...) Outcomes.
Consider the method signature: public int indexOf(String target) Which statement best describes the method’s behavior for our MyString class?
🔗
  • It returns the first index where target is found, or -1 if no match. Empty or null target returns 0, and any target longer than the string returns -1.
  • Correct! We treat null as an empty string, return 0 when the target is empty, and -1 if the match is impossible.
  • It throws an exception if target is null or if target is longer than the string.
  • No. Our simplified approach returns -1 for impossible matches and treats null as "" instead of throwing.
  • It searches only the first character of target and ignores the rest, returning 0 when found or 1 when not found.
  • No. We check all characters in target, not just the first one.
  • It ignores overlapping patterns, so indexOf("aaa") in "aaaa" returns -1.
  • No. Overlapping patterns are allowed. indexOf("aaa") in "aaaa" should find a match at index 0.
🔗
2. Multiple-Choice: lastIndexOf(...) Edge Cases.
When calling lastIndexOf(String target) on a MyString of length 6 (e.g. "banana"), which of the following is not how we handle special cases?
🔗
  • If target is null, we treat it as "" and return usedLength (which is 6 for "banana").
  • That is correct behavior (returns 6).
  • If target is "", we immediately return usedLength (6 for "banana").
  • That is correct behavior in our design.
  • We throw an exception if target is longer than usedLength, to indicate the search is impossible.
  • Correct—this is not what we do. We return -1 instead of throwing an exception.
  • If no match is found, we return -1.
  • Yes, that’s the expected behavior for no match.
🔗
3. Multiple-Choice: contains(...) Implementation.
Our contains(String target) method reuses indexOf internally. How does contains decide whether to return true or false for a given target?
🔗
  • It compares each character of target to each character of MyString, returning true if any matches.
  • Not quite. We rely on indexOf to do that comparison logic for us.
  • It calls indexOf(target) and returns true if the result is not -1, otherwise false.
  • Exactly! That’s how we reuse existing code to avoid duplicating logic.
  • It calls lastIndexOf(target) first, and if that fails, calls indexOf(target) as a fallback.
  • No, we don’t need both. One search method is enough to check for a match.
  • It returns false for an empty target since that can’t be found in the string.
  • No. In our design, empty strings or null are considered found (returns true or 0 index for indexOf).
🔗
4. Multiple-Choice: Overlapping Matches.
Consider "aaaa" as our MyString, and we call indexOf("aaa") vs. lastIndexOf("aaa"). Which statement best describes how overlapping matches are handled?
🔗
  • indexOf("aaa") returns 0 (the first match), while lastIndexOf("aaa") returns 1 (the last match), even though they overlap.
  • Correct. The loops in each method check for the earliest or latest valid match.
  • indexOf("aaa") returns 0, but lastIndexOf("aaa") fails to find a match and returns -1 due to the overlap.
  • No. Overlaps are allowed; we do find "aaa" at index 1 from the right side.
  • Both return 0 because the substring’s first occurrence is also the last occurrence when overlapping is disallowed.
  • No, we do allow overlapping. The last occurrence is at index 1, not 0.
  • Both throw exceptions to indicate an overlapping substring is not valid.
  • No. We never throw exceptions for overlapping matches; we handle them normally.
🔗
5. Multiple-Choice: Searching Method Summary.
Which of the following statements best summarizes our overall design and error policy for indexOf, lastIndexOf, and contains in MyString?
🔗
    • Throw a NullPointerException if target is null
    • Return 0 for empty target in all cases
    • Use exceptions for substring not found
  • No. We never throw exceptions; we have a simplified approach returning special values (like -1).
    • Always case-insensitive: "banana" matches "ANA"
    • Reject empty or null target by returning -1
    • Overlap checks cause exceptions
  • No. Our design is case-sensitive, treats empty or null as valid, and doesn’t throw exceptions on overlaps.
    • Treat null as an empty string
    • Return -1 if target is not found or if longer than the MyString
    • Return 0 for empty target in indexOf, and usedLength for empty in lastIndexOf
    • contains just checks if indexOf is -1 or not
  • Exactly! This encapsulates our simplified approach to searching and error handling.
    • Implicitly resizes if target is bigger than 100 chars
    • For empty or null target, returns any random index from 0–usedLength
    • Requires separate logic for contains
  • No. We do no resizing, don’t return random indexes, and contains reuses indexOf.
🔗
6. Short-Answer: Handling "Impossible Matches".
When target is longer than the MyString or when no match is found, we return -1 instead of throwing an exception. In your own words, why might this be beneficial in some educational or prototyping contexts rather than strictly following real Java’s exceptions?
🔗
Answer.
🔗
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext