My DFS solution (C++)


  • 0
    Y

    class Solution
    {
    public:
    bool wordBreak(string s, unordered_set<string> &dict) {
    if (dict.size() < 1)
    return false;

    	if (s.length() < 1)
    		return false;
    
    	int len = s.length();
    	vector < bool > visited(len, false);
    	stack < int > DFS;
    
    	vector < int > dict_len (dict.size(), 0);
    	int i=0;
    	for (unordered_set<string>::iterator itr = dict.begin(); itr!=dict.end(); ++itr)
    	{
    		dict_len[i++] = (*itr).length(); 
    	}
    	sort(dict_len.begin(), dict_len.end());
    
    	DFS.push(0);
    
    	while (!DFS.empty())
    	{
    		int pos = DFS.top();
    		DFS.pop();
    
    		if (visited[pos] == false)
    		{
    			visited[pos] = true;
    			for (int i=0; i<dict_len.size(); ++i)
    			{
    				if (pos + dict_len[i] > s.length())
    					break;
    				string tmp = s.substr(pos, dict_len[i]);
    				if (dict.find(tmp) != dict.end())
    				{
    					if (pos + dict_len[i] == s.length())
    						return true;
    					DFS.push(pos + dict_len[i]);
    				}
    			// for (int i=0; i<dict_len.size(); ++i)
    			}
    		// if (visited[pos] == false)
    		}
    	// while (!DFS.empty())
    	}
    
    	return false;
    }
    

    };


Log in to reply
 

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