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.

思路很简单,明显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)){
                if(j == needle.length()) return haystack.substring(i);
        return null;

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s