Clear c++ codes 90 lines easy to understand


  • 0
    L
    class Solution {
    public:
    	int diffCount(const string &a, const string &b) {
    		int ret = 0;
    		for (int i = 0; i < (int) a.size(); i++) {
    			ret += (a[i] != b[i]);
    		}
    		return ret;
    	}
    	void constructMap(vector<int>* g, string beginWord, string endWord,
    			vector<string> &wordList) {
    		int n = wordList.size();
    		for (int i = 0; i < n; i++) {
    			for (int j = i + 1; j < n; j++) {
    				if (diffCount(wordList[i], wordList[j]) == 1) {
    					g[i].push_back(j);
    					if (i != 0 && j != n - 1)
    						g[j].push_back(i);
    				}
    			}
    		}
    	}
    	void bfs(vector<int>* g, vector<int>* ret, int n) {
    		vector<bool> vi(n + 2, false);
    		queue<int> qu;
    		qu.push(0);
    		vi[0] = true;
    
    		while (!qu.empty()) {
    			int len = qu.size();
    			vector<int> viSet;
    			while (len--) {
    				int s = qu.front();
    				qu.pop();
    				for (int i = 0; i < (int) g[s].size(); i++) {
    					int t = g[s][i];
    					if (vi[t] == false) {
    						if (ret[t].empty()) {
    							qu.push(t);
    							viSet.push_back(t);
    						}
    						ret[t].push_back(s);
    					}
    
    				}
    			}
    			for (int i = 0; i < (int) viSet.size(); i++) {
    				vi[viSet[i]] = true;
    			}
    			if (vi[n - 1] == true)
    				return;
    		}
    	}
    	void dfs(vector<vector<string> > &ret, vector<int> *ans, int t,
    			vector<string> &tmp, vector<string> &wordList) {
    		if (t == 0) {
    			tmp.push_back(wordList[0]);
    			ret.push_back(tmp);
    			tmp.pop_back();
    			return;
    		}
    		tmp.push_back(wordList[t]);
    		for (int i = 0; i < (int) ans[t].size(); i++) {
    			dfs(ret, ans, ans[t][i], tmp, wordList);
    		}
    		tmp.pop_back();
    	}
    	vector<vector<string> > findLadders(string beginWord, string endWord,
    			unordered_set<string> &wordList) {
    		vector<vector<string> > ret;
    		vector<string> vwordList;
    		vwordList.push_back(beginWord);
    		for (unordered_set<string>::iterator it = wordList.begin(); it != wordList.end();
    				it++) {			
    			vwordList.push_back(*it);
    		}
    		vwordList.push_back(endWord);
    
    		int n = vwordList.size();
    		vector<int> g[n], ans[n];
    		constructMap(g, beginWord, endWord, vwordList);
    		bfs(g, ans, n);
    		vector<string> tmp;
    		dfs(ret, ans, n-1, tmp, vwordList);
    		for (int i = 0; i < (int) ret.size(); i++) {
    			reverse(ret[i].begin(), ret[i].end());
    		}
    		return ret;
    	}
    };

Log in to reply
 

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