Rarbin Karp Solution with a tiny hash function


  • 0
    L

    I design a tiny hash function which calculates the sum of target String.

    If two string are anagrams each other, the sum of them would be the same. This is what the tiny hash function would do!

    In this way we could filter a lot of wrong answers when Iterating the source string. And in every iteration we can minus the most left and add the rightest elements(Sliding window).

    When sum is same and we get a hit, we judge if the two string are same.

    The average time complexity is O(m + n). But in some worthest cases, you know, the string occasionally add up same always, that would be another scenario!

    public class Solution {
        /**
         * @param s a string
         * @param p a non-empty string
         * @return a list of index
         */
        public List<Integer> findAnagrams(String s, String p) {
            // Write your code here
            int targetHash = hashInt(p);
            int sourceHash = 0;
            List<Integer> result = new ArrayList<>();
            if (s.isEmpty() || s.length() < p.length()) {
                return result;
            }
            
            
            for (int i = 0; i < s.length(); i++) {
                sourceHash += s.charAt(i);
                if (i >= p.length()) {
                    sourceHash -= s.charAt(i - p.length());
                }
                if (i >= p.length() - 1) {
                    if (sourceHash == targetHash) {
                        int currIndex = i - p.length() + 1;
                        if(isAnagram(s.substring(currIndex, i + 1), p)) {
                            result.add(currIndex);
                        }
                    }
                }
            }
            return result;
        }
        
        private int hashInt(String p) {
            int sum = 0;
            for (int i = 0; i < p.length(); i++) {
                sum += p.charAt(i);
            }
            return sum;
        }
        
        private boolean isAnagram(String source, String target) {
            int[] sourceMap = new int[charToIndex('z') + 1];
            for (int i = 0; i < source.length(); i++) {
            	sourceMap[charToIndex(source.charAt(i))] += 1;
                sourceMap[charToIndex(target.charAt(i))] -= 1;
            }
            
            for (int i : sourceMap) {
                if (i != 0) {
                    return false;
                }
            }
            return true;
        }
        
        private int charToIndex(char target) {
            return target - 97;
        }
    }
    

Log in to reply
 

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