首页 > 代码库 > Word Break
Word Break
139. Word Break
题目链接:https://leetcode.com/problems/word-break/#/description
题目大意:给定一个非空字符串s和一个单词列表wordDict,列表里的单词没有空字符串,并且没有重复,要求判断字符串s可否分割成wordDict里的单词。
思路:用动态规划的思想,定义dp[i]为s字符串的子串s.substr(0,i)是否可以被分割成wordDict里的单词,那么状态转移方程为dp[i]=true if s.substr(0,i) in wordDict || dp[j]==true && s.substr(j+1,i-j) in wordDict (0<j<i),else dp[i]=false。
算法复杂度分析:时间复杂度O(n^2),空间复杂度O(n)。
代码:
1 class Solution { 2 public: 3 bool wordBreak(string s, vector<string>& wordDict) { 4 unordered_set<string> wordSet; 5 vector<bool> dp(s.size() + 1, false); 6 dp[0] = true; 7 for (auto word : wordDict) 8 wordSet.emplace(word); 9 for (int i = 1; i <= s.size(); ++i) 10 for (int j = 0; j < i; ++j) 11 if (dp[j]) { 12 auto word = s.substr(j, i - j); 13 if (wordSet.find(word) != wordSet.end()) { 14 dp[i] = true; 15 break; 16 } 17 } 18 return dp[s.size()]; 19 } 20 };
评测系统上运行结果:
Word Break
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。