leetcode 472. Concatenated Words 字符串拼接判定 + 动态规划DP实现

港控/mmm° 2022-06-03 02:50 68阅读 0赞

Given a list of words (without duplicates), please write a program that returns all concatenated words in the given list of words.  
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example:  
Input: \[“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”\]

Output: \[“catsdogcats”,”dogcatsdog”,”ratcatdogcat”\]

Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;  
“dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;  
“ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.  
Note:  
The number of elements of the given array will not exceed 10,000  
The length sum of elements in the given array will not exceed 600,000.  
All the input string will only include lower case letters.  
The returned elements order does not matter.

题意很简单，就是在一个dict中寻找可以有其他字符串组成的复合字符串，这道题是[leetcode 139. Word Break DP + DFS按照index递归搜索][leetcode 139. Word Break DP _ DFS_index] 的一个升级，**这道题再一次的提醒要注意复习前面的习题**

就是一个DP动态规划的做法

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) 
        {
            vector<string> res;
            set<string> dict(words.begin(),words.end());
            for (string word : words)
            {
                if (word.size() <= 0)
                    continue;
                //这里删除word是为了避免一些很小的元素出现在res中
                dict.erase(word);
                vector<bool> dp(word.length()+1,false);
                dp[0] = true;
                for (int i = 1; i <= word.size(); i++)
                {
                    for (int j = 0; j < i; j++)
                    {
                        if (dp[j] == true && dict.find(word.substr(j, (i - 1) - j + 1)) != dict.end())
                        {
                            dp[i] = true;
                            break;
                        }
                    }
                }
                if (dp[word.length()] == true)
                    res.push_back(word);
                dict.insert(word);
            }
            return res;
        }
    };

[leetcode 139. Word Break DP _ DFS_index]: http://blog.csdn.net/jackzhang_123/article/details/78009135