My 7ms solution different from the 'standard' solution


  • 0
    L

    Just made my 7ms solution which is different from the to some extend 'standard' solution which I saw in most places,

    The places I might kinda of dislike the standard solution are:

    • Each index of the offset is checked. Using the "leetcode" in the problem description as example, we checked the second char 'e', third char 'e' and so forth ..
    • the type of parameter wordDict as unordered_set is a cheat. When you code as 'wordDict.find(s.substr(j,i))', it`s a cheat. Checking up against a collection of strings as dictionary entry generally requires O(n) time if Trie is not used.

    Not a coding expert, and please let me know your comments.

    class Solution {
    public:
    	bool wordBreak(std::string s, std::unordered_set<std::string>& wordDict) {
    
    		std::unordered_set<size_t> segmentables, currSegmentables;
    
    		for (const std::string& word : wordDict)
    		{
    			if (word.length() > s.length())
    				continue;
    			if (s.compare(0, word.length(), word) == 0)
    			{
    				if (s.length() == word.length())
    					return true;
    				currSegmentables.insert(word.length());
    			}
    		}
    
    		while (currSegmentables.empty() == false)
    		{
    			std::unordered_set<size_t> newSegmentables;
    
    			for (size_t start : currSegmentables)
    			{
    				for (const std::string& word : wordDict)
    				{
    					if (start + word.length() > s.length())
    						continue;
    					if (segmentables.find(start + word.length()) != segmentables.end()) // Here is the DP
    						continue;
    
    					if (s.compare(start, word.length(), word) == 0)
    					{
    						if (start + word.length() == s.length())
    							return true;
    
    						newSegmentables.insert(start + word.length());
    						segmentables.insert(start + word.length());
    					}
    				}
    			}
    
    			currSegmentables.swap(newSegmentables);
    		}
    
    		return false;
    	}
    };

Log in to reply
 

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