leetcode || 139、Word Break

1462 단어 LeetCodedp
problem:
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" .
Hide Tags
 
Dynamic Programming
thinking:
s의 첫 번째 알파벳에서 뒤로 일치합니다. i 앞의 접두사가 일치할 수 있다면 s 문자열 i 뒤의 접두사가 일치하는지 확인하십시오
code:
class Solution{
    public:
bool wordBreakHelper(string s, unordered_set<string> &dict,set<string> &unmatch) {
        if(s.length() < 1) return true;
		bool flag = false;
		for(int i = 1; i <= s.length(); i++)
		{
			string prefixstr = s.substr(0,i);
			unordered_set<string>::iterator it = dict.find(prefixstr);
			if(it != dict.end())
			{
				string suffixstr = s.substr(i);
				set<string>::iterator its = unmatch.find(suffixstr);
				if(its != unmatch.end())continue;
				else{
					flag = wordBreakHelper(suffixstr,dict,unmatch);
					if(flag) return true;
					else unmatch.insert(suffixstr);
				}
			}
		}
		return false;
    }
	bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
		if(len < 1) return true;
		set<string> unmatch;
		return wordBreakHelper(s,dict,unmatch);
    }
};

좋은 웹페이지 즐겨찾기