CY-Left

LeetCode基本功底

[leetcode]Number of Matching Subsequences

792. Number of Matching Subsequences 寻找子串数量

原题&翻译

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

给出一个字符串 S 和一个单词字典 words,判断 words[i] 是否为 S 的子串。

举个例子 :
给出:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
分析: words 中有三个字符串是 S 的子串,分别为 "a", "acd", "ace".
  • S 和 Words 中所有字符均为小写字母。

  • S 长度在 [1, 50000] 范围内。

  • words 长度限制在 [1, 5000] 范围内。

  • words 中的字符串长度限制在 [1, 50] 范围内。


解题思路

超时的方法

把超时方法也列出来,是因为它可能有点价值吧,哦那个通常的方法处理这道题,比如这个代码,挨个匹配,妥妥的超时。

public:
int numMatchingSubseq(string S, vector<string>& words) {
        int sum=0;
        int SLen = S.size();
        for(int i=0; i<words.size(); i++){
            int m=0;
            int n=0;
            while(1){
                if(words[i][n] == S[m]) {m++;n++;}
                else {m++;}
                if(m>SLen) {break;}
                if(n==words[i].size()) {sum++;break;}
            }
        }
        return sum;
    }
};

不超时的方法

这里呢,我们注意到一共就 26 个字母,我们只需要处理一下原数据,把原来的 S 的索引按照字符顺序存入 letter(26) 中。和 words[i] 匹配的时候,只需要判断该字母是否存在于 letter 中即可(还需要判断索引是否大于之前)。两百多 ms,还是很慢的。

class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {
    vector <vector<int>> letter(26);

    int SLen = S.size();
    int sum=0;

    for(int i=0;i<SLen;i++){
        letter[S[i]-'a'].push_back(i);
    }

    for(int i=0; i<words.size(); i++){
        int flag = -1;
        int status = 0;
        for(int j=0;j<words[i].size();j++){
            for(int k=0;k<letter[ words[i][j]-'a' ].size();k++){
                if(letter[ words[i][j]-'a' ][k] > flag) {flag = letter[ words[i][j]-'a' ][k]; status++; break;}
            }
        }

        if(status==words[i].size()) sum++;
    }

    return sum;
}
};

春草年年绿,王孙归不归?

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=657