My AC java solution, rolling hash but hash function is very simple


  • 0
    M
    public class Solution {
        public int strStr(String haystack, String needle) {
            
            if (haystack == null || needle == null){
                return -1;
            }
            
            if (needle.equals("")){
                return 0;
            }
            
            if (needle.length() > haystack.length()){
                return -1;
            }
            
            int needleHash = 0;
            for (int i=0; i<needle.length(); i++){
                needleHash += new Character(needle.charAt(i)).hashCode();            
            }
            
            int currentHayStackHash = 0;
            for (int i=0; i<needle.length(); i++){
                currentHayStackHash += new Character(haystack.charAt(i)).hashCode();            
            }
            
            if (needleHash == currentHayStackHash){
                if (subStrEqual(haystack, 0, needle))
                    return 0;
            }
            
            for (int i=1; i<=haystack.length()- needle.length(); i++){
                currentHayStackHash -= new Character(haystack.charAt(i-1)).hashCode();
                currentHayStackHash +=  new Character(haystack.charAt(i + needle.length() - 1)).hashCode();
                if (needleHash == currentHayStackHash){
                    if (subStrEqual(haystack, i, needle))
                        return i;
                }
            }
            
            return -1;
        }
        
        
        private boolean subStrEqual(String str, int index, String subStr){
            boolean same = true;
            for (int i=index; i<index + subStr.length(); i++){
                if (str.charAt(i) != subStr.charAt(i-index)){
                    same = false;
                    break;
                }
            }
            return same;
        }
    }

  • 0
    R
    This post is deleted!

Log in to reply
 

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