LintCode 594. 字符串查找 II

原题

解

第一步，万年不变的查错。如果给的string是null或target是null，那么直接return。

    public int strStr2(String source, String target) {
        if (source == null || target == null) {
            return -1;
        }
        ...
    }

看一下target的长度，如果是0，那就直接return。

        int m = target.length();
        if (m == 0) {
            return 0;
        }

初始化一下power，这个power是用来在sliding window时，去掉左边的character的hash的。最后如果找到hash一样的了，还要再逐字对比一下，因为hash有可能有冲突。

        int power = 1;
        for (int i = 0; i < m; i++) {
            power = (power * 31) % BASE;
        }

先计算一下target的hash code。

        int targetCode = 0;
        for (int i = 0; i < m; i++) {
            targetCode = (targetCode * 31 + target.charAt(i)) % BASE;
        }

然后一个sliding window来找每个substring的hashCode。当source code 加上右边一个character，就要减掉左边的一个character。

        int sourceCode = 0;
        for (int i = 0; i < source.length(); i++) {
            sourceCode = (sourceCode * 31 + source.charAt(i)) % BASE;
            if (i <= m - 1) {
                continue;
            }
            
            sourceCode = (sourceCode - power * source.charAt(i - m)) % BASE;
            if (sourceCode < 0) {
                sourceCode += BASE;
            }
            
            if (sourceCode == targetCode) {
                String match = source.substring(i - m + 1, i + 1);
                if (match.equals(target)) {
                    return i - m + 1;
                }
            }
        }

完整的code

public class Solution {
    private static final Integer BASE = 100000;
    /*
     * @param source: A source string
     * @param target: A target string
     * @return: An integer as index
     */
    public int strStr2(String source, String target) {
        if (source == null || target == null) {
            return -1;
        }
        
        int m = target.length();
        if (m == 0) {
            return 0;
        }
        
        int power = 1;
        for (int i = 0; i < m; i++) {
            power = (power * 31) % BASE;
        }
        
        int targetCode = 0;
        for (int i = 0; i < m; i++) {
            targetCode = (targetCode * 31 + target.charAt(i)) % BASE;
        }
        
        int sourceCode = 0;
        for (int i = 0; i < source.length(); i++) {
            sourceCode = (sourceCode * 31 + source.charAt(i)) % BASE;
            if (i <= m - 1) {
                continue;
            }
            
            sourceCode = (sourceCode - power * source.charAt(i - m)) % BASE;
            if (sourceCode < 0) {
                sourceCode += BASE;
            }
            
            if (sourceCode == targetCode) {
                String match = source.substring(i - m + 1, i + 1);
                if (match.equals(target)) {
                    return i - m + 1;
                }
            }
        }
        
        return -1;
        
    }
}

分析

时间复杂度

是O(n + m)，n是source的长度，m是target的长度。

空间复杂度

O(1)。

这个算法的根本就是hash。把一串字符串变成可直接对比的数字。然后通过加右边的hash，减左边的hash来做到每一个字符串的hash都是O(1)。