Home > Reflections | ⏮️ ⏭️

2024-08-14

🧠 Education

Influence

🏋 Coding Practice

28. Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

🪞 Reflections

1. After reviewing the official solutions, it was a good idea to go with brute force.
   1. Arguably, I should have reached this conclusion sooner.
2. Testing
   1. During manual testing, I found and fixed several indexing errors
   2. However, the one blunder stayed: continue where break was intended
      1. A silly mistake
      2. one that I recognized not too long after a failed submission
3. This feels like a good warm up for my interview later today
   1. Not too stressful
   2. Gets me coding and re-familiarizes me with my process

⌨️ My Solution

/* Find index of first occurrence of needle in haystack  
1. Brute force:  
  - scan left to right  
  - upon finding first index, check subsequent indices for a match  
runtime complexity: O(N^2)  
extra space complexity: O(1)  
inefficiency lies in the fact that we may scan the same substrings repeatedly  
  
Can we pre-scan to avoid repetition?  
How do we remember where legitimate candidates exist?  
[9:29] let's just brute force it first  
[13:06] done with initial implementation  
[17:07] Finished test; first submission  
bugs found after first submission:  
1. Wrong Answer: leetcode, leeto (1 != -1)  
2. whoops: break instead of continuing  
[18:43] Successful submission  
*/  
function strStr1(haystack: string, needle: string): number { // sasadb, sad  
  for (let i = 0; i < haystack.length; i++) { // 2; 1; 0  
    for (let j = 0; j < needle.length; j++) { // 2; 1; 0; 2; 1; 0  
      if (haystack[i + j] !== needle[j]) break // T; T; T; F; F; T; T  
      if (j === needle.length - 1) return i // T => return 2  
    }  
  }  
  return -1  
};  
  
// let's just use the built-in indexOf  
function strStr(haystack: string, needle: string): number {  
  return haystack.indexOf(needle)  
};