[LeetCode] Implement strStr()

Problem:

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Solution 1:O(n^2)

public class Solution {
    public String strStr(String haystack, String needle) {
        int len1 = haystack.length();

 int len2 = needle.length();

 if (len2 == len1 && len2 == 0)
  return "";
 
 if (len2 == 0)
     return haystack;
 
 for (int i = 0; i < len1; i++) {
     if (len1 - i + 1 < len2)
         return null;
 
     int k = i;
     int j = 0;
 
     while (j < len2 && k < len1 && needle.charAt(j) == haystack.charAt(k)) {
         j++;
         k++;
  if (j == len2)
      return haystack.substring(i);
     }
 }
 return null;
    }
}

Solution2 O(n^2)

public class Solution {
    public String strStr(String haystack, String needle) {
        if(haystack == null || needle == null )
            return null;
        
        if(needle.length() == 0)
         return  haystack;
            
        ArrayList list = new ArrayList();
        int start = -1;
        for(int i=0; i<=haystack.length() - needle.length();i++){
            if(haystack.charAt(i)!= needle.charAt(0))
                continue;
            if(needle.length() == 1){
             start = i;
                break;
            }    
            boolean isFind = true;
            for(int t=1; t< needle.length();t++){
                if(haystack.charAt(i+t) == needle.charAt(0)){
                    list.add(i+t);
                }
                
                if(haystack.charAt(i+t) != needle.charAt(t)){
                    if(list.size() >0){
                        i= list.remove(0)-1;
                    }
                    else{
                        i = i+t;
                    }
                    isFind = false;
                    break;
                }
            }    
            if(isFind){
             start = i;
             break;
            }
        }
        if(start >=0){
            return haystack.substring(start);
        }
        else{
            return null;
        }
    }
}

Key concept: Solution2 use arraylist to store possible starting point