lintcode23. 字典中的子序列

忘是亡心i 2023-07-06 04:55 34阅读 0赞

给一字串s和单词的字典dict，请返回字典中所有是s的子序列的单词。  
子序列的定义是：如果字符串s通过去掉部分字母可以变成字符串t，那么t是s的子序列

样例
    样例 1:
    
    输入："lintcode"，["de","ding","co","code","lint"]
    输出：["de","co","code","lint"]
    解释
    我们可以删去"lintco"得到"de"。
    我们可以删去"lint"和"de"得到"co"。
    我们可以删去"lint"得到"code"。
    我们可以删去"code"得到"lint"。
    我们无法得到"ding"。
    样例 2:
    
    输入："a"，[]
    输出：[]
    解释：字典为空
    挑战
    如果字符串长度s小于等于100\,000100000应当怎么做？
    
    注意事项
    字符串s的长度小于等于1\,0001000。
    
    字典中的单词数量小于等于1\,0001000，单词长度总和小于等于1\,0001000。
    
    所有字符串只包含小写字母。

class Solution {
        
    public:
        /**
         * @param s: a string
         * @param wordDict: A set of words.
         * @return: All correct words
         */
        vector<string> wordSubsequence(string &s, unordered_set<string> &wordDict) {
        
            // write your code here
            int len=s.size();
            vector<string> res;
            if(len==0) return res;
            for (auto word : wordDict) {
        
                /* code */
                if(search(s,word))res.push_back(word);
            }
            return res;
        }
        bool search(string s,string word)
        {
        
            int sindex=0;
            for (int i = 0; i < word.size(); i++) {
        
                /* code */
                while(sindex<s.size()&&s[sindex]!= word[i]) sindex++;
                if(sindex==s.size()) return false;
                sindex++;
            }
            return true;
        }
    };