Implement strStr(), Leetcode 解题笔记

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
首先理解题意,因为java里没用过strStr()这方法,所以还真是用了一些时间才搞明白。一开始以为是从haystack里返回第一个与needle相同的substring,写完后发现不对,应该是返回这个substring和其之后的所有字符。

思路很简单,明显two pointers循环,但是很难一次写对,主要是特殊条件的判断,以及超时的优化需要注意。

public class Solution {
    public String strStr(String haystack, String needle) {
        
        if(haystack.length() == needle.length() && needle.length() == 0) return "";
        if(needle.length() == 0) return haystack;
        
        for(int i = 0; i < haystack.length(); i++){
            int k = i;
            int j = 0;
            
            //must check length otherwise time limit exceeded. 
            if(haystack.length() - i + 1 < needle.length()) return null;
            
            while(k < haystack.length() && haystack.charAt(k) == needle.charAt(j)){
                k++;
                j++;
                if(j == needle.length()) return haystack.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