首页 > 编程学习 > 139. 单词拆分 与 140. 单词拆分 II

139. 单词拆分 与 140. 单词拆分 II

发布时间:2022/9/9 21:58:24

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

 

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意,你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

 

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • swordDict[i] 仅有小写英文字母组成
  • wordDict 中的所有字符串 互不相同
  • 解析: 多重背包就是
  • 背包重量为s总长度,每个单词的重量为自己的长度,价值也为自己的长度,当装满时价值最高,最高为s长度

话说注意:

01背包和多重背包写法

class Solution {
public:

    bool wordBreak(string s, vector<string>& wordDict) {
        int dp[310];
        memset(dp, 0, sizeof(dp));
        // for(int i = 0; i < wordDict.size(); i++)
        // {
        //     int m = wordDict[i].size();
        //     for(int j = s.length() - 1; j >= m - 1; j--)
        //     {
        //         int k = j;
        //         while(k >= j - m + 1)
        //         {
        //             if(s[k] != wordDict[i][m - 1 - (j - k)])
        //                 break;
        //             k--;
        //         }
        //         if(k >= j - m + 1) continue;
        //         if(j - m < 0) dp[j] = max(dp[j], m);
        //         else dp[j] = max(dp[j], dp[j - m] + m);
        //         cout << j << "  " << dp[j] << endl;
        //     }
        // }

        for(int j = 0; j < s.length(); j++)
        {
            for(int i = 0; i < wordDict.size(); i++)
            {
                int m = wordDict[i].size();
                if(j - m + 1 >= 0)
                {
                    int k = j;
                    while(k >= j - m + 1)
                    {
                        if(s[k] != wordDict[i][m - 1 - (j - k)])
                            break;
                        k--;
                    }
                    if(k >= j - m + 1) continue;
                    if(j - m < 0) dp[j] = max(dp[j], m);
                    else dp[j] = max(dp[j], dp[j - m] + m);
                }

            }


        }




        // cout << dp[s.length() - 1] << endl;
        return dp[s.length() - 1] == s.length();



    }
};

 

 

单词拆分II

我用的字典树,一年前写的题

不知道unordered_map可不可以过

class Solution {
public:
    int tree[10010][26];
    bool vis[10010];
    int cnt;
    vector<string> v;
    void build(string str)
    {
        int len = str.length();
        int rt = 0;
        for(int i = 0; i < len; i++)
        {
            int x = str[i] - 'a';
            if(tree[rt][x] == 0)
            {
                tree[rt][x] = ++cnt;
            }
            rt =  tree[rt][x];
        }
        vis[rt] = 1;
    }
    void dfs(string s, int k, string str)
    {
        if(k >= s.length())
        {
            v.push_back(str);
            return;
        }
        int rt = 0;
        int len = s.length();
        string tmp = "";
        while(k < len)
        {
            int x = s[k] - 'a';
            rt = tree[rt][x];
            if(rt == 0) break;
            tmp += s[k];
            if(vis[rt])
                dfs(s, k + 1, str == "" ? str + tmp : str + " " + tmp);
            k++;

        }
    }



    vector<string> wordBreak(string s, vector<string>& wordDict) {
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        memset(tree, 0, sizeof(tree));
        int len = wordDict.size();
        for(int i = 0; i < len; i++)
        {
            build(wordDict[i]);
        }
        dfs(s, 0, "");
        return v;
 
    }
};

 

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号