Why my codes run time exceeded DFS return minPath


  • 0
    Z
    class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
            vector<string> refSet;
            int minPath = 0;
            
            if (beginWord.size() != endWord.size() || beginWord.size() == 0) return 0;
            
            unordered_set<string> path;
            path.insert(beginWord);
            
            minPath = dfs(beginWord, endWord, wordDict, 0, path);
            
            return (minPath == INT_MAX ? 0: (minPath +1));
        }
        
        int dfs(string& beginStr, string& endStr, unordered_set<string>& wordDict, int depth, unordered_set<string> & path)
        {
            if (strEqual(beginStr, endStr))
            {
                return depth;
            }
            
            int minDepth = INT_MAX;
            int curDepth = 0;
            
            for (auto it = wordDict.begin(); it != wordDict.end(); it++)
            {
                string tmpStr = *it;
                if (bOneLetterDiff(beginStr, tmpStr) && path.find(tmpStr) == path.end() )
                {
                    path.insert(tmpStr);
                    curDepth = dfs(tmpStr, endStr, wordDict, depth+1, path);
                    path.erase(path.find(tmpStr), path.end());
                    if (curDepth < minDepth)
                        minDepth = curDepth;
                }
            }
            
            return minDepth;
        }
        
        bool bOneLetterDiff(string& beginStr, string& endStr)
        {
            if (beginStr.size() != endStr.size()) return false;
            int countDiff = 0;
            for (int i = 0; i < beginStr.size(); i++)
            {
                if (beginStr[i] != endStr[i])
                {
                    countDiff++;
                }
            }
            
            return (countDiff == 1);
        }
        
        bool strEqual(string& beginStr, string& endStr)
        {
            if (beginStr.size() != endStr.size()) return false;
            
            for (int i = 0 ; i< endStr.size(); i++)
            {
                if (beginStr[i] != endStr[i])
                    return false;
            }
            
            return true;
        }
    };

Log in to reply
 

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