lintcode 284. 匹配子序列的单词

向右看齐 2023-07-04 03:20 3阅读 0赞

给定字符串 source 和单词字典 words, 返回所有 words 中是 source 的子序列的单词。

样例
    示例 1:
    输入: 
    source = "abcde"
    words = ["a", "bb", "acd", "ace"]
    输出: ["a", "acd", "ace"]
    解释: 有三个是 source 的子序列的单词: "a", "acd", "ace"。
    示例2 :
    输入: 
    source = "bcogtadsjofisdhklasdj"
    word = ["book","code","tag"]
    输出: ["book"]
    解释: 仅有一个是 source 的子序列的单词: "book"
    挑战
    source的长度范围是 [1, 100000].
    words中所有单词长度之和的长度范围是 [1, 1000].
    注意事项
    source 和 words 中的字符保证都是大小写字母组成的
    source的长度范围是 [1, 1000].
    words中所有单词长度之和的长度范围是 [1, 1000].
    words中包含的单词个数范围是 [1, 1000].

class Solution {
        
    public:
        /**
         * @param source: A string
         * @param words: A list of string
         * @return: return list of words[i] that is a subsequence of source.
         */
        vector<string> MatchingSubsequences(string &source, vector<string> &words) {
        
            // write your code here
            int slen=source.size();
            int wlen=words.size();
            vector<int>count(wlen,0);
            for (int i = 0; i < slen; i++) {
        
                /* code */
                for(int j = 0; j < wlen; j++)
                {
        
                    if(count[j]==INT_MAX) continue;
                    if(source[i]==words[j][count[j]]) count[j]++;
                    if(count[j]==words[j].size()) count[j]=INT_MAX;
                }
            }
            vector<string> res;
            for (int i = 0; i < wlen; i++) {
        
                /* code */
                if(count[i]==INT_MAX) res.push_back(words[i]);
            }
            return res;
        }
    };