LEETCODE 792. Number of Matching Subsequences 解题思路分析

题目大意:

匹配子序列的单词数

给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。

示例:
输入: 
 S = "abcde"
 words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。

注意:

  • 所有在words和 S 里的单词都只由小写字母组成。
  • S 的长度在 [1, 50000]。
  • words 的长度在 [1, 5000]。
  • words[i]的长度在[1, 50]。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=792

解题思路分析:

个人感觉这道中等题目的难度略微偏高。解题时,我们需要使用每个字典中的单词去和S比较,看它是否是S的子序列。不过这种比较非常耗费时间,因此我们需要对S进行一下预处理。首先定义一个二维数组arr[][],其中 arr[i][j]代表距离S中第i位字符最近的j字符的位置。换句话说,我们需要遍历一边字符串,记录下字符串S每一位上的字符,在它右侧距离它最近的a-z分别在哪。

做好预处理之后,我们使用字典中的每一个单词与arr进行比较。首先定义2个下标分别表示当前单词的下标index,以及S中对应的下标indexAtS。我们通过 arr[indexAtS][index]可以判断出距离S当前下标之后最近的index所指向的字符位置,如果位置为0,说明 indexAtS 之后不存在该字符(indexAtS 之后的下标一定大于0),退出继续比较下一个单词。如果存在, indexAtS 赋值为 arr[indexAtS][index],同时 index 加一,继续寻找下一个字符,直到所有字符都存在为止,此时找到一个合理子序列,返回结果加一。

另外上述逻辑有一个小漏洞,如果当前单词的首字符与S的首字符相同,那么在第一次调用arr[indexAtS][index]时,可能无法得到正确答案。详细处理可以参照代码:

public int numMatchingSubseq(String S, String[] words) {
    // 预处理用的数组
    int[][] arr = new int[S.length()][26];
    // 预处理
    for(int i=S.length()-2;i>=0;i--){
        arr[i]=Arrays.copyOf(arr[i+1],26);
        arr[i][S.charAt(i+1)-'a']=i+1;
    }
    // 比较每一个单词
    int res=0;
    for(String s : words){
        // 对应S的下标
        int indexAtS=0;
        // 当前单词下标
        int index=0;
        // 如果当前单词首字符等于S首字符
        if(s.charAt(0)==S.charAt(0)){
            // 当前单词下标加一
            index++;
            // 如果当前单词长度只有1,说明当前单词已经遍历结束,结果加一
            if(s.length()==1) res++;
        } 
        // 继续比较单词接下来的字符,在S中是否存在
        while(index<s.length()){
            // 当前字符
            int c=s.charAt(index)-'a';
            // 如果indexAtS之后不存在c,当前单词不合法
            if(arr[indexAtS][c]==0) break;
            // 将indexAtS更新为c在S中的位置
            indexAtS=arr[indexAtS][c];
            // index加一
            // 如果index为单词最后一位,代表单词中所有字符均在S中找到
            if(++index==s.length()) res++;
        }
    }
    return res;
}

本题解法执行时间为81ms。

Runtime: 81 ms, faster than 60.45% of Java online submissions for Number of Matching Subsequences.

Memory Usage: 58.4 MB, less than 12.50% of Java online submissions for Number of Matching Subsequences.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-792-number-of-matching-subsequences-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。