首页 > 代码库 > Word Break
Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
思路：使用动态规划策略，Q[i]记录从s[0]到s[i]是否存在合法路径。
求解Q[i]时，依次遍历Q[j](j=i-1,i-2,...,0)，若Q[k]为true且s.substr(j+1,i-j)是合法单词，则说明Q[i]经过Q[j]能合法到达s[0]，且过渡单词为s.substr(j+1,i-j)，于是将Q[i]置为true，并跳出内循环继续求解Q[i+1]。
1 class Solution { 2 public: 3 bool wordBreak( string s, unordered_set<string> &dict ) { 4 if( s.empty() ) { return true; } 5 if( dict.empty() ) { return false; } 6 vector<bool> Q( s.length(), false ); 7 for( int i = 0; i < (int)s.length(); ++i ) { 8 for( int j = i; j > 0; --j ) { 9 if( Q[j-1] && dict.count( s.substr( j, i-j+1 ) ) ) { Q[i] = true; break; }10 }11 if( !Q[i] && dict.count( s.substr( 0, i+1 ) ) ) { Q[i] = true; }12 }13 return Q.back();14 }15 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。