lint题目120 单词接龙 实现

描述

题目链接：https://www.lintcode.com/problem/120/

给出两个单词（start和end）和一个字典，找出从start到end的最短转换序列，输出最短序列的长度。

变换规则如下：
每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中)

其他：
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
len(dict) <= 5000, len(start) < 5len(dict)<=5000,len(start)<5

样例

样例 1：

输入：

start = "a"
end = "c"
dict =["a","b","c"]
1
2
3

输出：

2
1

解释：

"a"->"c"
1

样例 2：

输入：

start ="hit"
end = "cog"
dict =["hot","dot","dog","lot","log"]
1
2
3

输出：

5
1

解释：

"hit"->"hot"->"dot"->"dog"->"cog"
1

解题思路

正向变换：从start->end的变换思路
优先在dict中查找与start仅一处不同，该位与end该位相同的字符串
找不到则查找与start仅一位不同的字符串。
该思路有问题：当字符串位数比较多，会出现查找start仅一位不同的字符串，比优先在dict中查找与start仅一处不同，该位与end该位相同的字符串的情况变换要小的情况。

初始化
创建currents字符串组，用于存放待变换字符
创建currentsSwap字符串组，用于与current进行交换(因为在循环中需要对currents进行更改，防止更改时，迭代器由于更改出现问题，因此利用currentsSwap避免该问题)

定义变换顺序组tfMap

将start字符串添加到currents字符串组及tfMap
currents字符串组赋值给currentsSwap字符串组

while(currents字符串组不为空)
{
    遍历currents (auto current : currents) {
        查看current与end是否相同
          相同：则结束；
          不同：则比较current与end区别，出现不同位，则将current该位对应替换为end该位字符，得到与current字符串只有一个不同的候选字符串数组tmpstr
          遍历tmpstr数组 （tmpstr[i] : tmpstr）{
             判断tmpstr[i]是否存在于dict中，
                 存在：判断tmpstr[i]与end是否相同，相同：则进行结束退出处理；不相同：将其推入currentsSwap中，并覆盖current；
          }

          tmpstr中不存在dict中的字符串，则在dict中查找与current字符串相差一位的字符串tmpstr1，推入currentsSwap中，并覆盖current；

          tmpstr1为空(在dict中查找不存在与current字符串相差一位的字符串)，则将current从currentsSwap中删除了
    }

    currents = currentsSwap;

}

到达次数，说明没有找到变换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

//比较两个字符串有几位不同，返回不同的位数
int strcmpn (const string &str1, const string &str2)
{
  if (str1.size() != str2.size()) {
    return -1;
  }

  //for (auto t : str1) {
  int c = 0;
  for (int i = 0; i < str1.size(); i++) {
    if (str1[i] != str2[i]) {
       c++;
    }
  }

  return c;
}

//比较两个字符串是否只有一个不同，并输出该位置的索引值
int strcmp1 (const string &str1, const string &str2)
{
  if (str1.size() != str2.size()) {
    return -1;
  }

  //for (auto t : str1) {
  int c = 0;
  int loc = -1;
  for (int i = 0; i < str1.size(); i++) {
    if (str1[i] != str2[i]) {
       c++;
       loc = i;
    }
  }

  if (c == 1) {
    return loc;
  } else {
    return -1;
  }
}

//提取start到end转换可能的z变换字符串组
int tfExtract(const string &start, const string &end, vector<string> &tfStrs)
{
  int c = 0;

  for (int i = 0; i < start.size(); i++) {
    if (start[i] != end[i]) {
      string ts = start;
      ts.replace(i, 1, end.substr(i,1));
      tfStrs.push_back(ts);
      c++;
    }
  }

  return c;
}

//在dict中提取与str只有一处不同的字符串
int tfExtract(const string &str, const unordered_set<string> &dict, vector<string> &tfStrs)
{
  int c = 0;

  for (auto it : dict) {
    if (strcmpn(str, it) == 1) {
      tfStrs.push_back(it);
      c++;
    }
  }

  return c;
}

int ladderLength(string &start, string &end, unordered_set<string> &dict)
{
  map<int, string> currents;
  map<int, string> currentsSwap;
  map<int, vector<string>> tfMap;

  currents[0] = start;
  currentsSwap = currents;
  
  vector<string> tfS;
  tfS.push_back(start);
  tfMap[0] = tfS;

  while(currents.size()) {
    // For debug
    //sleep(2);

    for (auto it = currents.begin(); it != currents.end(); it++) {
      string current = it->second;
      //判断current与end的不同
      if (current == end) {
        cout << "Find a transform: " << tfMap[it->first].size() << endl;
        for (auto ts : tfMap[it->first]) {
          if (ts != end) {
            cout << ts << "->";
          } else {
            cout << ts << endl;
          }
        }

        return tfMap[it->first].size();
      }

      vector<string> tmpstr;
      tfExtract(current, end, tmpstr);

      int ind = 0;
      for (int i = 0; i < tmpstr.size(); i++) {
        if (tmpstr[i] == end) {
          tfMap[it->first].push_back(end);
          cout << "Find a transform: " << tfMap[it->first].size() << endl;
          for (auto ts : tfMap[it->first]) {
            if (ts != end) {
              cout << ts << "->";
            } else {
              cout << ts << endl;
            }
          }
  
          return tfMap[it->first].size();
        }

        //TODO:会不会出现有比tmpstr要快的从tmpstr1的变换，或者从tmpstr中变换不出，而tmpstr1可以
        //可以反向寻找从end->start的变换，这样可以避免该问题
        if (dict.find(tmpstr[i]) != dict.end()) {
          //currentsSwap  counts 索引保持一致就可以
          currentsSwap[it->first + ind] = tmpstr[i];
          vector<string> tfS(tfMap[it->first]);
          tfS.push_back(tmpstr[i]);
          tfMap[it->first + ind] = tfS;
          ind++;
        }
      }

      vector<string> tmpstr1;
      if (!ind) {
        if (tfExtract(current, dict, tmpstr1) > 0) {
          for(int j = 0; j < tmpstr1.size(); j++) {
            //防止出现循环
            for (auto tt : currentsSwap) {
              if (tt.second == tmpstr1[j]) {
                currentsSwap.erase(tt.first);
                tfMap.erase(tt.first);
                continue;
              }
            }

            currentsSwap[it->first + ind] = tmpstr1[j];
            vector<string> tfS(tfMap[it->first]);
            tfS.push_back(tmpstr1[j]);
            tfMap[it->first + ind] = tfS;
            ind++;
          }
        } else {
          currentsSwap.erase(it->first);
          tfMap.erase(it->first);
        }
      }
    }

    currents = currentsSwap;
    //TODO:delete
    //cout << "currents size: " << currents.size() << endl;

    //for (auto tt:currentsSwap) {cout << tt.first << ": " << tt.second << " ";}
    //cout << endl;

    //for (auto tfMit : tfMap) {
    //  for (auto ts: tfMit.second) {cout << ts << endl;}
    //  cout << "*****************" << endl;
    //}

  }


  cout << "There is no solution to transformation start to end" << endl;

  return -1;
}

int main ()
{
  unordered_set<string> dict;
  string start;
  string end;

  cout << "Pls enter the start word (Press enter to end):" ;
  getline(cin, start);
  cout << "Pls enter the end word (Press enter to end):" ;
  getline(cin, end);

  string ts;
  cout << "Pls enter the dictory words (Press enter to end):" ;
  //while (getline(cin, ts, ' ')) {
  getline(cin, ts);

  istringstream record(ts);
  while (record >> ts) {
      dict.emplace(ts);
  }

  cout << "start: " << start << endl;
  cout << "end: " << end << endl;
  cout << "dict:" << endl;
  for (auto it : dict) {
    cout << it << " ";
  }
  cout << endl;

  return ladderLength(start, end, dict);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226

运行结果

样例1：

Pls enter the start word (Press enter to end):a
Pls enter the end word (Press enter to end):c
Pls enter the dictory words (Press enter to end):a b c
start: a
end: c
dict:
c a b
Find a transform: 2
a->c

样例2：

Pls enter the start word (Press enter to end):hit
Pls enter the end word (Press enter to end):cog
Pls enter the dictory words (Press enter to end):hot dot dog lot log
start: hit
end: cog
dict:
log lot dog hot dot
Find word hot in dictory
currentsSwap: 0 hot
0: hot
***Find word lot in dictory
currentsSwap: 0 lot
***Find word dot in dictory
currentsSwap: 1 dot
0: lot 1: dot
Find word log in dictory
currentsSwap: 0 log
Find word dog in dictory
currentsSwap: 1 dog
0: log 1: dog
Find a transform: 5
hit->hot->lot->log->cog

样例2中，该方法优先找到hit->hot->lot->log->cog这样的变换。从log中也可以看出该算法也找出了"hit"->“hot”->“dot”->“dog”->"cog"的变换方式，只是由于使用 unordered_set的dict将lot排在了dot之前。所以先找到谁就是以谁先为结束。