Leetcode–Implement strStr()

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;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s