Implement strStr() [LeetCode 7]

RSS

Implement strStr() [LeetCode 7]

16 Jul

Frequency: ♥ ♥ ♥ ♥ ♥ Difficulty: ♥ ♥ ♥
Data Structure: String
Algorithm: brute force, Rolling Hash，KMP, Rabin-Karp，Boyer-Moore

Problem Description

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

问题分析

这是一个经典问题，虽然一开始没读懂干嘛。。。判断一个字符串（needle）是否是另一个（haystack）的子串，如果是，则返回haystack中第一次出现needle字符串开始直到末尾的substring（题目中的pointer应该是对C++而言）。看了网上资料，对这个问题有很多比较经典的算法，如KMP，Rabin-Karp，Boyer-Moore algorithms，有兴趣的读者可以进行深入了解（我不生产算法，我只做算法的搬运工，哈哈）。

解法一

在没有相关算法的基础上，我们也只能老老实实地进行brute force搜索了。假设haystack长度为N，needle长度为M，则我们需要比较从haystack每一个字符开始的substring（当然可以有小小的优化），但是时间复杂度仍然是O(N*M)，空间复杂度为O(1)。

// traverse every char of haystack from left to right
//   - compare the substring from this char with needle (char by char)
//     - if not equal, break
//   - if equal, return
public class Solution {
    public String strStr(String haystack, String needle) {
        if(haystack == null || needle == null)
            return null;
        int i, j;
        for(i = 0; i <= haystack.length() - needle.length(); i++) {
            for(j = 0; j < needle.length(); j++) {
                if(haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if(j == needle.length()) {
                return haystack.substring(i);
            }
        }
        return null;
    }
}

解法二

然后由一个比较容易理解的线性算法Rolling Hash，这个解法是Code Ganker博客中贴出来的。其优化的思想就是我们能不能用一种方法来记录之前遍历过的substring，这样在每次失败的情况下，能不用再跑回去重新一个字符一个字符的检测。答案是有的，它的基本思想是将一个字符串（needle长度）映射为一个hashcode，为了保证相同的字符串code值相同，不同的字符串code值不同，需要用一个比字符集大的素数为底，每个字符index为幂。

haystring = “abacde”, needle = “bacde”
“abacd” => hashcode (h1) = 1 + 2*29 + 1*29^2 + 3*29^3 + 4*29*4;
“bacde” => hashcode (h2) = h1/29 + 5*29^4;

有了这个基础，我们需要做的第一步就是从haystring中取出最开始的一段字符串（needle长度），计算它的hashcode，然后从左往右每次移动一个字符，更新hashcode，并与needle的hashcode比较，直到找到相等的substring。过程中每一次更新都是constant的操作，所以检测所有子串的时间复杂度只需要O(N)。但是如同那些经典算法，我觉得在面试的时候写出来是不实际的（大牛勿喷），所以权当开开眼界好了。

public class Solution {
    public String strStr(String haystack, String needle) {
        if(haystack==null || needle==null||haystack.length()<needle.length()) return null;
        if(needle.length()==0) return haystack;
        int base = 29;
        long needleHash = 0;
        long tempBase = 1;
        // get the hashcode for the needle
        for(int i=needle.length()-1; i>=0; i--){
            needleHash += (long) needle.charAt(i) * tempBase;
            tempBase *= base;
        }
        long hayHash = 0;
        tempBase = 1;
        // get the hashcode for the first substring of haystack
        for(int i=needle.length()-1; i>=0; i--){
            hayHash += (long) haystack.charAt(i) * tempBase;
            tempBase *= base;
        }
        tempBase /= base;
        // check the first substring
        if(hayHash == needleHash) return haystack;
        // traverse the rest substring, get hashcode and check
        for(int i=needle.length(); i<haystack.length(); i++){
            hayHash = (hayHash - (long) haystack.charAt(i-needle.length()) * tempBase) * base + (long) haystack.charAt(i);
            if(hayHash == needleHash){
                return haystack.substring(i-needle.length()+1);
            }
        }
        return null;
    }
}

补充

虽然有的题存在潜在的更优算法，但是在面试的过程中首先能有思路能上手才是王道，管你是不是brute force呢。就比如这道题，如果面试的时候较真一定要像个更好的算法才动手那估计是跪的节奏。。。所以遇到这种情况不要慌，先把逻辑清楚的brute force写出来，然后再和面试官讨论可能的优化，事实上很多题brute force都不好写的呢~

查看更多LeetCode解题思路…

Uzumaki Kyuubi