Python&C++ Solution, Simple and Direct.


  • 0
    Y

    ##Example:
    s = "helloword" dict = [hel, hello, llo, wo, word]

    you will get a back_list like that: back_list = [hel, lo, wo, rd]

    HOW TO JUDGE True or False?

    just compare len(s) and head

    when the while loop end, tail == len(s)+1

    if all words have a match in dict, head == len(s)

    ##Here is the Python code:

    class Solution:
    	# @param s, a string
    	# @param dict, a set of string
    	# @return a boolean
    	def wordBreak(self, s, dict):
    		head = 0
    		tail = head + 1
    		back_list = []
    		while tail<=len(s):
    			word = s[head:tail]
    			if word in dict:
    				back_list.append(word)
    				head = tail
    			else:
    				suffix = ''
    				for i in range(len(back_list)-1,-1,-1):
    					suffix = back_list[i] + suffix
    					if suffix+word in dict:
    						head = tail
    						back_list.append(word)
    						break
    			tail += 1
    		if head == len(s):
    			return True
    		return False
    

    ##C++ Code is similar to others'. Don't save substr but save index. save sapce

    class Solution{
    public:
        bool wordBreak(string s, unordered_set<string> &dict){
            int len = s.length();
    		deque<int> mark(1,0);
    		for(int i=1;i<len+1;i++){
    			for(int loop = 0;loop<mark.size();loop++){
    				int start = mark[loop];
    				string word = s.substr(start,i-start);
    				auto iterator = dict.find(word);
    				if(iterator!=dict.end()){
    					mark.push_front(i);
    					break;
    				}
    			}
    		}
    		if(len==mark[0])
    			return true;
    		else
    			return false;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.