C++ DFS Solution. Simple to understand.


  • 0
    S
    class Solution {
    public:
    	int diff(string start, string end) {
    		bool f = 0;
    		for (int i = 0; i<start.size(); i++) {
    			if (start[i] != end[i]) {
    				if (f)
    					return 0;
    				f = 1;
    			}
    		}
    		return 1;
    	}
    //Helper and the function following are almost similar. You can easily follow it.
    	int helper(string start, string end, vector<string>& bank, unordered_set<string>& set, int count) {
    		if (count>bank.size())
    			return -1;
    		if (start == end)
    			return count;
    		int x = -1; int res = INT_MAX;
    		for (string word : bank) {
    			if (diff(start, word) && set.find(word) == set.end()) {
    				set.insert(word);
    				x = helper(word, end, bank, set, count+1);
    				if (x>0)
    					res = res<x ? res: x;
    				set.erase(word);
    			}
    		}
    		if (res == INT_MAX)
    			return -1;
    		return res;
    
    	}
    	int minMutation(string start, string end, vector<string>& bank) {
    		if (!bank.size())
    			return -1;
    		unordered_set<string> set;
    		int x=-1, count = INT_MAX;
    		for (string word : bank) {
    			if (diff(start, word) && set.find(word) == set.end()) {
    				set.insert(word);
    				x = helper(word, end, bank, set, 1);
    				if (x>0)
    					count = count<x ? count : x;
    				set.erase(word);
    			}
    		}
    		if (count == INT_MAX)
    			return -1;
    		return count;
    	}
    };
    

Log in to reply
 

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