lintcode 194. 寻找单词

刺骨的言语ヽ痛彻心扉 2023-07-03 12:15 95阅读 0赞

给定一个字符串str，和一个字典dict，你需要找出字典里的哪些单词是字符串的子序列，返回这些单词。

样例
    Example 1:
    
    Input:
    str="bcogtadsjofisdhklasdj"
    dict=["book","code","tag"]
    Output:
    ["book"]
    Explanation:Only book is a subsequence of str
    Example 2:
    
    Input:
    str="nmownhiterer"
    dict=["nowhere","monitor","moniter"]
    Output:
    ["nowhere","moniter"]
    挑战
    |str|<=100000
    
    注意事项
    |str|<=1000
    the sum of all words length in dictionary<=1000
    (All characters are in lowercase)

思路:  
1、建立一个index数组记录dict中已经判定相同的位置  
2、遍历str，如果str字符与dict\[i\]中某个目前需判断字符相同，则index\[i\]加一后移。  
3、如果index\[i\]和dict\[i\]的长度相同，说明dict\[i\]存在str中。  
注意：不可判定两者index\[i\]和dict\[i\]的长度相同则将dict\[i\]保存到结果中，因为题目要求按照原字典顺序保存

class Solution {
        
    public:
        /**
         * @param str: the string
         * @param dict: the dictionary
         * @return: return words which  are subsequences of the string
         */
        vector<string> findWords(string &str, vector<string> &dict) {
        
            // Write your code here.
            int len=dict.size();
            vector<int> index(len,0);
            vector<string> res;
            for (int i = 0; i < str.size(); i++) {
        
                /* code */
                for(int j = 0; j < len ; j++)
                {
        
                    if(index[j]==INT_MAX) continue;
                    else if(dict[j][index[j]]==str[i])    index[j]++;
                    if(index[j]==dict[j].size()) index[j]=INT_MAX;
                }
            }
            for (int i = 0; i < len; i++) {
        
                /* code */
                if(index[i]==INT_MAX) res.push_back(dict[i]);
            }
            return res;
        }
        
    };