【每日算法Day 19】字符串基础1

今天的这几题都是基于比较的字符串处理问题，包括字符串子串匹配（逐个扫描匹配与基于滚动哈希的匹配），最长公共前缀（纵向扫描法与排序后比较）与最后一个单词的长度（单词的判定与几种特殊情况）。

LeetCode 28. 实现 strStr() (opens new window)

题目描述

实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例

输入: haystack = "hello", needle = "ll"
输出: 2

解题思路

这一题要实现的函数功能等同于String类提供的方法indexOf(String subStr)，记haystack.length()为n，needle.length()为m。首先特殊情况：m为空串时，空串为任何字符串的子串，返回0；n为空串时，除了空串之外任何字符串都不是其子串，返回-1；

最直接的方法就是将haystack从[0~n-m]的每一位与needle的首字符比较，相同时再截取后面等长度的子串与needle比较，相同返回当前index，找到最后也没有相同的子串则返回-1。

public int strStr(String haystack, String needle) {
    if (needle==null||needle.length()==0) return 0;
    if (haystack==null||haystack.length()==0) return -1;
    char first=needle.charAt(0);
    //m>n时needle必然不可能是子串，循环也不会执行，直接返回-1
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        if (haystack.charAt(i) == first && haystack.substring(i, i + needle.length()).equals(needle)) {
            return i;
        }
    }
    return -1;
}

该方法的时间复杂度为O((n-m)*m)，空间复杂度为O(1)。

还可以了解一下Rabin–Karp算法 (opens new window)，是一种基于滚动哈希对滑动窗口在常数时间内生成哈希码来匹配子串与目标串的算法。

我基于滚动哈希也写了一下，采用的哈希函数是更简单的字符ASCII码相加，不过更容易出现碰撞，所以在哈希值相同时还要再验证下子串是否相同。算法先计算初始哈希，再计算滚动哈希，理论时间复杂度为O(m)+O(n-m)，空间复杂度为O(1)。不过该种算法时间复杂度常数项较大，在字符串较短的时候实际运行不会比第一种方法更快。

public int strStr(String haystack, String needle) {
    if (needle==null||needle.length()==0) return 0;
    if (haystack==null||haystack.length()==0) return -1;

    int n=haystack.length(),m=needle.length();
    if (n<m) return -1;

    int haystackHash=initialHash(haystack,m),needleHash=initialHash(needle,m);
    for (int i = 0; i <= n - m; i++) {
        if (i != 0) {
            haystackHash=haystackHash-(int)haystack.charAt(i-1)+(int)haystack.charAt(i+m-1);
        }
        if (haystackHash == needleHash && haystack.substring(i, i + needle.length()).equals(needle)) {
            return i;
        }
    }
    return -1;
}

private int initialHash(String str, int endIndex) {
    int hash=0;
    for (int i = 0; i < endIndex; i++) {
        hash+=(int)str.charAt(i);
    }
    return hash;
}

LeetCode 14. 最长公共前缀 (opens new window)

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。

示例

输入: ["flower","flow","flight"]
输出: "fl"

解题思路

纵向扫描法：首先找到输入的所有字符串的最小长度L，则用于扫描前缀的指针i大小不会超过L-1。接下来对于每个i，比较每个str.charAt(i)是否相同，一旦发现不同返回[0,i-1]的子串，扫描完L-1位后都没有发现不同，则返回[0,L-1]的子串。

public String longestCommonPrefix(String[] strs) {
    //数组本身为空或不含元素则返回空串
    if (strs==null||strs.length==0) return "";
    int minLength=Integer.MAX_VALUE;
    for (String str : strs) {
        //扫描最小长度的过程中如果发现空串则返回空串
        if (str==null||str.length()==0) return "";
        minLength=Math.min(minLength,str.length());
    }
    //到这里数组的第一个字符串肯定不是空串
    char c=strs[0].charAt(0);
    for (int i = 0; i < minLength; i++) {
        for (String str : strs) {
            if (str.charAt(i)!=c)
                return strs[0].substring(0,i);
        }
    }
    return strs[0].substring(0,minLength);
}

记数组元素个数为n，最短字符串的长度为m，则该算法的时间复杂度为O(n)+O(m*n)，空间复杂度为O(1)。

力扣上还介绍了二分、分治的做法，不过时间空间复杂度并没有降低，有的甚至还提高了，感觉有点为了用而用的意思。

我还看到了一种虽然理论复杂度提高了但思路简洁明了挺有意思的算法：首先按照字典序对数组进行排序，再比较第一个字符串和最后一个字符串输出公共前缀。记数组中最长字符串的长度为l，则排序的时间复杂度为O(l*nlogn)。两种算法在LeetCode上执行的时间都是1ms。

public String longestCommonPrefix2(String[] strs){
    if (strs==null||strs.length==0) return "";
    Arrays.sort(strs);
    String first=strs[0],last=strs[strs.length-1];
    int i=0;
    for (; i < first.length() && i < last.length(); i++) {
        if (first.charAt(i)!=last.charAt(i))
            return first.substring(0,i);
    }
    return first;
}

LeetCode 58. 最后一个单词的长度 (opens new window)

题目描述

给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

示例

输入: "Hello World"
输出: 5

解题思路

从后往前扫描字符串，以第一个不为空格的字符位置或者字符串首位为endIndex，再从endIndex出发，扫描到第一个为空格或者字符串首位时停下。如果是扫描到空格停下的，则长度为endIndex-i。如果扫描到字符串首位都没有发现空格，则长度为endIndex+1。

public int lengthOfLastWord(String s) {
    if (s==null||s.length()==0) return 0;
    int endIndex=s.length()-1;
    while (endIndex >= 0 && s.charAt(endIndex) == ' ' ) {
        endIndex--;
    }

    for (int i = endIndex; i >= 0; i--) {
        if (s.charAt(i)==' ')
            return endIndex-i;
    }
    return endIndex+1;
}