美文网首页
leetcode139 单词拆分

leetcode139 单词拆分

作者: 奥利奥蘸墨水 | 来源:发表于2020-01-03 22:04 被阅读0次

题目

题目

分析

使用hash表来存字典,然后对字符串s判断(i,j)位置间的字符串是否存在与字典中,存在的话,再判断(0,i-1)位置的字符串是否在字典中。
时间复杂度:O(n*n)。空间复杂度:O(n + m)。

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& words) {

        set<string> st(words.begin(), words.end());

        int len = s.size();
        vector<int> dp(len, 0);

        for (int i = 0; i < len; i++){
            for (int l = 1; i + l - 1 < len; l++){

                int j = i + l - 1;

                string str = s.substr(i, l);

                if (st.count(str) != 0 && (i - 1 >= 0 && dp[i - 1] == 1 || i == 0)){           
                    dp[j] = 1;
                }
            }
        }

        return dp[len - 1] == 1 ? true : false;
    }
};

相关文章

  • leetcode139 单词拆分

    题目 分析 使用hash表来存字典,然后对字符串s判断(i,j)位置间的字符串是否存在与字典中,存在的话,再判断(...

  • Leetcode139: 单词拆分

    给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在...

  • 单词拆分

    今天带着两个小姑娘一起在学而思网课上看英语视频,学到了一个单词拆分特别有趣,分享一下。 把 news 消息拆分为...

  • 单词拆分

    给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在...

  • 单词拆分

    给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在...

  • 单词拆分

    题目描述:给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一...

  • 单词拆分

    题目链接:(https://leetcode-cn.com/explore/interview/card/top-...

  • LeetCode-139-单词拆分

    LeetCode-139-单词拆分 139. 单词拆分[https://leetcode-cn.com/probl...

  • LeetCode-140-单词拆分 II

    LeetCode-140-单词拆分 II 140. 单词拆分 II[https://leetcode-cn.com...

  • 139. 单词拆分

    139. 单词拆分

网友评论

      本文标题:leetcode139 单词拆分

      本文链接:https://www.haomeiwen.com/subject/zlvtactx.html