The Problem:
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
Notes:
1. Be careful of empty string cases.
2. In the while loop when haystack reaches the end, means no match found, and what’s left after index i is already shorter in length than needle, so no need to proceed, should return null instead of break.
Java Solution-I
public class Solution { public String strStr(String haystack, String needle) { if(needle.length()==0) return haystack; //---!!!---check needle first, for case of both empty if(haystack.length()==0 )return null; int j = 0; for(int i = 0; i < haystack.length(); i++){ int temp = i; while(haystack.charAt(i)==needle.charAt(j)){ i++; j++; if(j==needle.length()){ return haystack.substring(i-needle.length()); } if(i == haystack.length()) return null; } i = temp; j = 0; //---!!!!!!!---j start from zero again } if(j==needle.length()){ //---!!!!!!---case that both ended return haystack.substring(haystack.length()-needle.length()); } return null; } }
Java Solution-II
public String strStr(String s, String t) { if(t.length() > s.length()) return null; if(t.length() == 0) return s; for(int i = 0; i < s.length(); i++){ if(s.charAt(i)==t.charAt(0)){ if(i+ t.length() <= s.length() && t.equals(s.substring(i, i+ t.length()))){ return s.substring(i); } } } return null; }