- class Solution {
- public:
- int ladderLength(string beginWord, string endWord, vector& wordList) {
- vector vis(wordList.size(),0);
- int res = INT_MAX;
- DFS(beginWord,endWord,wordList,res,vis);
- if(res == INT_MAX) return 0;
- else return res+1;
- }
- bool comp(string s1,string s2){
- int cnt = 0;
- for(int i=0;i <s1.size();i++){
- if(s1[i] != s2[i]) cnt++;
- }
- if(cnt == 1) return true;
- else return false;
- }
- void DFS(string beginWord, string endWord, vector wordList,int& res,vector vis){
- if(beginWord == endWord){
- int cnt = 0;
- for(int i=0;i < vis.size();i++){
- if(vis[i] == 1)cnt++;
- }
- res = min(res,cnt);
- }
- for(int i=0;i < wordList.size();i++){
- if(!vis[i] && comp(beginWord,wordList[i])){
- vis[i] = 1;
- DFS(wordList[i],endWord,wordList,res,vis);
- vis[i] = 0;
- }
- }
- }
- };
_DFS 写炸了, 研究一下 BFS
来源: http://www.bubuko.com/infodetail-2949197.html