Accepted solution using Boyer-Moore


  • 3
    F
    public class Solution {
    public String strStr(String haystack, String needle) 
    {
        if(haystack== null) return null;
        if(needle==null || needle.length()==0) return haystack;
        if(needle.length()>haystack.length()) return null;
    
        int pat_length = needle.length();
        int right[] = new int[256];
    
        for(int i=0;i<256;i++)
          right[i] =-1;
        for(int i=0;i<pat_length;i++)
          right[needle.charAt(i)] =i;
    
        int rtn = search(right,haystack,needle);
        if(rtn == haystack.length()) return null;
        else 
            return haystack.substring(rtn);
    }
    public int search(int[] right, String haystack,String needle)
    {
        int M = haystack.length();
        int N = needle.length();
        int i,j;
        int skip =0;
        for(i=0; i<=M-N; i+=skip)
        {
            skip =0;
            for(j=N-1;j>=0;j--)
            {
                if(needle.charAt(j)!=haystack.charAt(i+j))
                {
                    skip = j-right[haystack.charAt(j+i)];
                    if(skip<=0) skip=1;
                    break;
                }
            }
            if(skip ==0) return i;
        }
        return M;
    
    }
    

    }

    1. I tried DFA version of KMP, it turned out that it exceeds the time limit. I went back to the Algorithm book and checked time complexity of KMP(DFA version). Surprisingly, the typical runtime of KMP is same as brute force, which is 1.1N. It only improves the worst case runtime from NM to 2N. This is why leetcode accepts the brute force.
    2. The Boyer-Moore algorithm only needs O(N/M) for average runtime and O(NM) for worst case.
      Hope this helps. : )

  • 0
    Y

    my kmp solution using an array accepted


  • 0
    S

    I'm wondering what do you mean by "Brute force" here? I was thinking Brute force will take O(mn)。


  • 0
    F

    I am saying that the typical(means average) run time is 1.1N. But you are right, the worst case of brutal force is O(mn)


  • -1
    T

    Below is my answer got accepted:

    if(haystack == null || haystack.length() < needle.length())
    {
        return -1;
    }
    
    if(haystack.length() == 0 && needle.length()==0)
    {
        return 0;
    }
    for(int i = 0; i < haystack.length(); i++)
    {
        int j = 0;
        while(j < needle.length() && (haystack.length()-i-j-1) >= (needle.length()-j-1))
        {
            if(haystack.charAt(i + j) == needle.charAt(j))
            {
                j++;
            }
            else
            {
                break;
            }
        }
        
        if(j == needle.length())
        {
            return i;
        }
    }
    
    return -1;   

  • 0
    K

    my full dfa python code actually got accepted. dunno why the java one would time out though.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.