给定一个string数组dic及数组大小n，同时给定字典中的两个字符串串s和串t，为将s变到t，每次可以改变s中的任意一个字符，请返回由s到t变换所需的最少步数。同时需要满足在变换过程中的每个串都是字典中的串。若无法变换到t则返回-1。保证字符串长度均小于等于10，字典中字符串数量小于等于500。
测试样例：
["abc","adc","bdc","aaa”],4,”abc","bdc"
返回：2
[编程题]字符串变换
//参考了最前面的代码，按照自己的思路整理了一下；
public:
int countChanges(vector<string> dic, int n, string s, string t)
{
// write code here
if(s==t) return 0;//如果两个单词相同，变换0次即可;
vector<string>::iterator ite = find(dic.begin(),dic.end(),s);
int result = BFS(s,t,dic);
return result;
}
private:
int BFS(string start,string end,vector<string> &dict)
{
if(start == end) return 0;
// 存放单词和单词所在层次
queue<pair<string,int> > q;
q.push(make_pair(start,0));
// 判断是否访问过
vector<string> visited;
visited.push_back(start);
while(!q.empty())
{
pair<string,int> cur = q.front();
q.pop();
string word = cur.first;
int size = word.size();
// 穷尽所有可能的变换
for(int i=0;i<size;++i)
{
string newWord(word);
// 每次只变换一个字符,有26种可能
for(int j = 0;j < 26;++j)
{
newWord[i] = 'a'+j;
// 判断之前访问过或者是否在字典里
vector<string>::iterator ite = find(dict.begin(),dict.end(),newWord);
vector<string>::iterator ite2 = find(visited.begin(),visited.end(),newWord);
// 找到目标返回
if((ite!=dict.end()&&(newWord == end)))//判断存在于字典中，并且和目标字符串相同
{
return cur.second+1;
}
//没找到目标，那么就将该变换的字符串压入到visited中
if(ite2 == visited.end() && ite != dict.end())
{
visited.push_back(newWord);
q.push(make_pair(newWord,cur.second+1));
}
}
}
}
return -1;
}
};
发表于 2016-08-20 10:14:00
回复(1)
/*图的最短路径问题，首先构造距离矩阵，然后Floyd算法即可*/
class Change {
public:
bool path(string a, string b) {
int lenA = a.length(), lenB = b.length();
if (lenA != lenB) {
return false;
}
int flag = 0;
for (int i = 0; i < lenA; i++) {
if (a[i] != b[i]) {
if (flag == 0) {
flag++;
}
else {
return false;
}
}
}
return true;
}
int countChanges(vector<string> dic, int n, string s, string t) {
int map[500][500]; //题中明确说了不超过500个，so
int index_s, index_t;
for (int i = 0; i < n; i++) {
if (dic[i] == s) {
index_s = i;
}
if (dic[i] == t) {
index_t = i;
}
for (int j = i; j < n; j++) {
if (i == j) map[i][j] = 0;
else if (path(dic[i], dic[j])) {
map[i][j] = map[j][i] = 1;
}
else {
map[i][j] = map[j][i] = 500; //只有500个元素，最大距离不过500
}
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][k] + map[k][j] < map[i][j]) {
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
return (map[index_s][index_t] == 500) ? -1 : map[index_s][index_t];
}
};
发表于 2017-07-13 16:06:56
回复(1)
从目标字符串反推源字符串
#include<unordered_set>
class Change {
private:
int countDifference(const string& s1, const string& s2)
{
int res = 0;
for (int i = 0; i < s1.size(); ++i)
{
if (s1[i] != s2[i]) ++res;
}
return res;
}
public:
int countChanges(vector<string> dic, int n, string src, string target)
{
if (src == target) return 1;
if (src.size() != target.size()) return -1;
vector<int> dp(n, INT_MAX);
unordered_set<string> hs;
for (auto& s : dic) if (s.size() == src.size()) hs.emplace(s);
if (hs.find(target) == hs.end()) return -1;
hs.erase(target);
vector<string> cur{ target };
int res = 0;
while (true)
{
++res;
vector<string> next;
for (auto& s1 : cur)
{
for (auto& s2 : hs)
{
if (countDifference(s1, s2) == 1)
{
if (s2 == src) return res;
next.emplace_back(s2);
}
}
}
if (next.empty()) break;
for (auto& s : next) hs.erase(s);
cur = next;
}
return -1;
}
};
发表于 2017-07-02 18:20:17
回复(0)
bfs
import java.util.*;
public class Change {
public int countChanges(String[] dic, int n, String s, String t) {
Map<String ,List<String>> graph=new HashMap<>();
Set<String> dicSet=new HashSet<>(Arrays.asList(dic));
for (String s1 : dic) {
List<String> adj=getAdj(s1,dicSet);
graph.put(s1,adj);
}
Queue<String> queue=new ArrayDeque<>();
Map<String ,Integer> vistied=new HashMap<>();
vistied.put(s,0);
queue.add(s);
while(!queue.isEmpty()){
String te=queue.poll();
if (te.equals(t)) return vistied.get(t);
for (String s1 : graph.get(te)) {
if (null==vistied.get(s1)){
vistied.put(s1, vistied.get(te) + 1);
queue.add(s1);
}
}
}
return -1;
}
private List<String> getAdj(String s1, Set<String> dicSet) {
List<String> rst=new ArrayList<>();
for (int i = 0; i < 26; i++) {
for (int j = 0; j < s1.length(); j++) {
StringBuilder builder=new StringBuilder(s1);
builder.setCharAt(j, (char) ('a'+i));
if (dicSet.contains(builder.toString())&&!builder.toString().equals(s1)) rst.add(builder.toString());
}
}
return rst;
}
}
发表于 2016-08-17 16:09:30
回复(0)
BSF搜索最短路径：
class Change {
public:
bool isChanged(string a, string b)
{
int na = a.length(), nb = b.length(), diff = 0;
if(na != nb)
return false;
for(int i = 0; i < na; i++)
{
if(a[i] != b[i])
diff++;
}
return (diff == 1);
}
int countChanges(vector<string> dic, int n, string s, string t) {
// write code here
if(s == t)
return 0;
map<string, bool> visit;
//int size = dic.size();
for(int i = 0; i < n; i++)
visit[dic[i]] = false;
queue<string> q;
int res = 0, cur = 0, cur_num = 1, count = 0;
q.push(s);
while(!q.empty())
{
string temp = q.front();
q.pop();
if(temp == t)
return res;
//int len = temp.length();
for(int i = 0; i < n; i++)
{
if(!visit[dic[i]] && isChanged(temp, dic[i]))
{//cout << dic[i] << endl;
visit[dic[i]] = true;
q.push(dic[i]);
dic.erase(dic.begin() + i);
i--;
n--;
count++;
}
}
cur++;
if(cur == cur_num)
{
cur = 0;
cur_num = count;
count = 0;
res++;
}
}
return -1;
}
};
发表于 2016-05-26 13:42:55
回复(0)
["orw","t","dvctup","cxmiwt","acuwa","q","hg","zkhnpuuu","po","ba","sto","ej","tnpt","m","eiyni","pnc","okup","bdvjhbv","ba","lwjdr","b","tvtuh","wyqjisz","ml","ypf","j","xyzi","eymnyn","qqbghrf","oldn","zerolr","fitn","crqupizf","bb","dd","ujbxm","elfnxx","azc","u","gexzzx","k","skypumzi","vqn","zecpgiy","xbtc","twbc","uwkjjxju","sagstg","j","ghahwi","ohtlgcl","ki","bb","ik","xtqtmmi","fbntzw","bf","vwqneru","zi","ymcdjgf","caj","q","ixjvp","aa","g","oggviqjf","vvdtqww","eyz","iwrmag","zenpp","e","u","q","cfevty","foohwaw","zks","aj","yyo","uohpru","rfztkld","hxhsepv","mnpouez","jisck","iybztsqk","a","zreex","tfcr","yy"],88,"ej","bb"
这组数据。我觉得应该是 ej --> j(或者e) --> b --> bb 这样子三步完成，为什么让我输出的却是4呢？
发表于 2016-02-14 17:30:43
回复(1)
Solution: 使用Queue进行BFS，同时用一个HashSet来存储已经访问过的字符串。每访问完一个字符串（queue.poll()）就对该字符串进行替换：是否存在只变换一个字符的String在字典dic中，注意dic中有重复的字符串，所以我们可以使用一个HashSet来保存把重复的去掉。
public int countChanges(String[] dic, int n, String s, String t) {
// write code here
if(dic==null || n==0){
return 0;
}
HashSet<String> hash=new HashSet(); //记录访问过的string,同时可以判断某个string是否访问过
Queue<String> queue=new LinkedList<String>();
queue.offer(s);
hash.add(s);
int length=0; // 从0开始
while(!queue.isEmpty()){
length++; // 每进入循环一次，即步长+1
int size=queue.size();
for(int i=0;i<size;i++){ // 同一个level
String curr = queue.poll();
for(String next: getNext(curr,dic)){ // 满足条件的变换了的字符串
if(hash.contains(next)){
continue;
}
if(next.equals(t)){ //找到t字符串了就return
return length;
}
queue.offer(next); // 继续下一步的查找
hash.add(next);
}
}
}
return 0;
}
private List<String> getNext(String word, String[] dic){
List<String> result=new ArrayList<String>();
if(dic==null || dic.length==0) return result;
Set<String> set=new HashSet<String>(); //由于dic中有重复的字符串，使用HashSet来去掉重复的
for(String s:dic){
set.add(s);
}
for(char ch='a';ch<='z';ch++){
for(int i=0;i<word.length();i++){
if(word.charAt(i)==ch){
continue;
}
String newWord=replace(word,i,ch);
if(set.contains(newWord)){
result.add(newWord);
}
}
}
return result;
}
private String replace(String s,int i, char ch){
char[] arr=s.toCharArray();
arr[i]=ch;
return new String(arr);
}
发表于 2016-01-04 08:58:53
回复(1)
//类似于二叉树的层次遍历，每次选取能修改一个字符达到的节点
class Change {
public:
int countChanges(vector dic, int n, string s, string t) {
// write code here
queue q;
int min_step = 0;
int level_num = 1;
q.push(s);
vector flag(n,0);
string node_str;
while(!q.empty())
{
node_str = q.front();
q.pop();
level_num--;
if(node_str == t)
return min_step;
for(int i=0;i<n;++i)
{
if(flag[i]==0 && checkOneChage(dic[i], node_str))
{
flag[i] = 1;
q.push(dic[i]);
}
}
if(level_num==0)
{
min_step++;
level_num = q.size();
}
}
return -1;
}
bool checkOneChage(string& s,string& t)
{
if(s.size() != t.size())
{
return false;
}
int num = 0;
for(int i=0;i<s.size();++i)
{
if(s[i] != t[i])
num++;
}
return num == 1;
}
};
发表于 2020-07-09 22:14:54
回复(0)
class Change {
public: int BFS(vector<string> dic, string s, string e){ if(s==e) return 0; queue<pair<string,int>> q; q.push(make_pair(s,0)); vector<string> v; v.push_back(s); while(!q.empty()){ pair<string,int> p = q.front(); q.pop(); string w = p.first; int n = w.length(); for(int i=0;i<n;i++){ string t(w); for(int j=0;j<26;j++){ t[i] = 'a'+j; if(t==e) return p.second+1; if(find(dic.begin(),dic.end(),t)!=dic.end() && find(v.begin(),v.end(),t)==v.end()){ v.push_back(t); q.push(make_pair(t, p.second+1)); } } } } return -1; }
int countChanges(vector<string> dic, int n, string s, string t) {
if(s==t)
return 0; return BFS(dic,s,t);
}
};
发表于 2019-03-16 02:07:58
回复(0)
class Change:
def countChanges(self, dic, n, s, t):
v, q, trace = set(), [s], {}
v.add(s)
while len(q) > 0: # BFS
h = q.pop(0)
for x in [x for x in dic if x not in v and self.diff(h, x)]:
if x == t:
k = 1
while h != s:
k += 1
h = trace[h]
return k
else:
q.append(x)
v.add(x)
trace[x] = h
return -1
@staticmethod
def diff(a, b): # 找出只有一个字母不同的单词
k = 0
if len(a) == len(b):
for i in xrange(len(a)):
if a[i] != b[i]:
k += 1
elif k >= 2:
return False
return k == 1
发表于 2017-03-21 22:18:41
回复(0)
用dfs做的，在其中有三点很重要：第一，减枝，如果发现长度大于之前的，则直接return；
第二，首先在原始数据中删除重复数据；第三；再找到目标字符串后直接返回当前函数，不在此
基础上继续dfs。
class Change {
vector<string> vec;
int num;
int flag[505];
string aim;
int res=-1;
public:
int countChanges(vector<string> dic, int n, string s, string t) {
// write code here
sort(dic.begin(),dic.end());
dic.erase(unique(dic.begin(),dic.end()),dic.end());
for(int i=0;i<dic.size();i++){
vec.push_back(dic[i]);
}
num=dic.size();
aim=t;
res=0x3f3f3f3f;
memset(flag,0,sizeof(flag));
for(int i=0;i<n;i++){
if(dic[i]==s) flag[i]=1;
}
dfs(s,0);
if(res==0x3f3f3f3f) return -1;
return res;
}
void dfs(string s,int route){
if(route>res) return; //减枝，这个很重要
if(s==aim){
if(route<res) res=route;
return; //这里找到之后return
}
vector<int> vint;
for(int i=0;i<num;i++){
if(isymble(s,vec[i])){
vint.push_back(i);
}
}
for(int i=0;i<vint.size();i++){
if(flag[vint[i]]==1) continue;
else{
flag[vint[i]]=1;
dfs(vec[vint[i]],route+1);
flag[vint[i]]=0;
}
}
}
bool isymble(string str1,string str2){
int len1=str1.length();
int len2=str2.length();
if(len1!=len2) return false;
int diseq=0;
for(int i=0;i<len1;i++){
if(str1[i]!=str2[i]) diseq++;
}
if(diseq==0) return false;
if(diseq==1) return true;
return false;
}
};
发表于 2016-03-30 15:59:16
回复(0)
Python解法:说起来怎么现在只剩python2的编译器了,MD中文注释一直报错...
# -*- coding:utf-8 -*-
#可以看成从s到t是否可达,故用BFS
class Change:
def countChanges(self, dic, n, s, t):
path = dict()#用dict来存储target->start的路径
dic = set(dic)#去除dic中重复的节点
#用BFS
queue = [s]
visited = set()
all_count = []#所有路径的长度
while queue:
current_node = queue.pop(0)
# 对于current_node的所有邻居
for neibor in self.getNeibors(current_node, dic, visited):
if neibor == t:
path[neibor] = current_node
all_count.append( self.get_start_to_target_count(path, s, t))
else:
queue.append(neibor)
visited.add(neibor)#这里是neibor而不是current_node
path[neibor] = current_node
#返回最小的长度
if not all_count:
return -1
return min(all_count)
#根据path计算count
def get_start_to_target_count(self, path, start, target):
count = 0
while not target == start:
count += 1
target = path[target]
return count
#获取所有邻居
def getNeibors(self, current_node, dic, visited):
neibors = []
for node in dic:
#没有访问过的且差值相差1的
if not node in visited and self.diffCount(current_node, node):
neibors.append(node)
return neibors
#计算差值
def diffCount(self, current_node, node):
if not len(current_node) == len(node):
return False
count = 0
#每一位都比较
for i in range(len(current_node)):
if not current_node[i] == node[i]:
count += 1
if count > 1:
return False
if count == 1:
return True
发表于 2017-12-10 11:27:34
回复(0)
//BFS
int countChanges(vector<string> dic, int n, string s, string t) {
set<string>res(dic.begin(),dic.end());
res.erase(s);
queue<string>q;
q.push(s);
int f = 0,ans = 0;
while(res.size()){
int len = q.size();
while(len--){
string start = q.front();
if(start == t)return ans;
q.pop();
vector<string>tmp;
for(auto x:res){
if(valid(x,start)){
f = 1;
q.push(x);
tmp.push_back(x);
}
}
for(auto x:tmp)res.erase(x);
}
if(f)ans++;
f = 0;
}
return -1;
}
bool valid(string s1,string s2){
int len = s1.size();
if(len!=s2.size())return false;
int cnt = 0;
for(int i = 0;i<len;++i){
if(s1[i]!=s2[i])++cnt;
}
return cnt == 1;
}
编辑于 2019-09-08 19:30:52
回复(0)
1.由于变换法则是改变任意一个字符 故不存在添加 删除操作 所以长度不相同的词必定不能 2.两个词相同 直接返回0 3.若两个词长度为n 则需要先把dict中长度不是n的单词过滤掉 4.以s为起点，遍历由变换关系组建的图，因为是最少次数 故是宽度优先 采用队列 5.后面两个辅助函数负责找到字典中与词邻接的词 这里的邻接关系为 若s到t能通过 变化一个字符获得 则邻接 class Change: def countChanges(self, dic, n, s, t): """ 最短路径 宽度优先 数据结构为队列 """ if s == t: return 0 elif len(s) != len(t): return -1 else: length = len(s) dic_ = [] for word in dic: if len(word) == length: dic_.append(word) visited = [] queue = self.getlist(s,dic_) dis = 1 while queue: queue_ = [] while queue: cur = queue[0] queue.remove(queue[0]) if cur in visited: continue else: if cur == t: return dis else: visited.append(cur) queue_ += self.getlist(cur,dic_) dis += 1 queue = queue_ return -1 def is_common_1(self,s1,s2): ## 判断两个词之间是否可以变1来转化 length = len(s1) count = 0 for i in range(length): if s1[i] != s2[i]: count += 1 return (count == 1) def getlist(self,s,dic): list1 = [] for s_ in dic: if self.is_common_1(s,s_): list1.append(s_) else: continue return list1
发表于 2019-06-07 23:25:45
回复(0)
借鉴总结：
1. 利用iterator中的find函数，判断当前元素是否在容器中；
2. 利用BFS，广度优先遍历，遍历所有可能情况；
3. 利用BFS，需要记录已经访问过的元素，防止二次访问；
class Change {
public:int BFS(vector<string> dic, string s, string t){
if(s == t)
return 0;
vector<string> v;//存放已经变换得到的字符串
v.push_back(s);
queue<pair<string, int>> q;//存放字符串与变换次数
pair<string, int> tmp;
tmp = make_pair(s, 0);
q.push(tmp);
while(!q.empty()){
tmp = q.front();
q.pop();
for(int i = 0; i < tmp.first.size(); i++){//26个字母
string news = tmp.first;
for(int j = 0; j < 26; j++){
char tmpchar = j + 'a';
news[i] = tmpchar;
vector<string>::iterator ite1 = find(dic.begin(), dic.end(), news);
vector<string>::iterator ite2 = find(v.begin(), v.end(), news);
if(ite1 != dic.end() && ite2 == v.end()){//news在dic中&&还没变换得到
if(news == t)
return tmp.second + 1;
else{
pair<string, int> next(news, tmp.second + 1);
q.push(next);
v.push_back(news);
}
}
}
}
}
return -1;
}
int countChanges(vector<string> dic, int n, string s, string t) {
// write code here
vector<string>::iterator ite1 = find(dic.begin(), dic.end(), s);
vector<string>::iterator ite2 = find(dic.begin(), dic.end(), t);
if(ite1 != dic.end() && ite2 != dic.end())//s与t都在dic中
return BFS(dic, s, t);
else
return -1;
}
};
发表于 2019-04-18 16:47:24
回复(0)
import java.util.*;
public class Change {
public int countChanges(String[] dic, int n, String s, String t) {
if (dic == null || n <= 0 || s.length() != t.length())
return -1;
if (s.equals(t))
return 0;
Map<String, Integer> map = new HashMap<>();//记录当前字符串被改变的次数
LinkedList<String> queue = new LinkedList<>();//BFS的队列
map.put(s, 0);
queue.add(s);
while (!queue.isEmpty()) {
String top = queue.peek();
List<String> adjs = getAdjStr(dic, n, top);//获取当前字符串的邻接字符串（只有一位不相同的字符串）
for (String adj : adjs) {
if (adj.equals(t)) {//当前变换已经与目的字符串一致
return map.get(top) + 1;//因为是邻接的关系，所以需要+1
} else {
if (map.get(adj) == null) {
map.put(adj, map.get(top) + 1);//因为是邻接的关系，所以需要+1
queue.add(adj);
}
}
}
}
return -1;
}
public List<String> getAdjStr(String[] dic, int n, String s) {
List<String> adjs = new ArrayList<>();//存放邻接字符串
String t;
int count;//记录不同字符的个数
for (int i = 0; i < n; i++) {
t = dic[i];
count = 0;
if (s.length() != t.length())//长度不一致的不做判断
continue;
int j = 0;
for (; j < s.length(); j++) {//逐位比较，如果不同位数超过1，直接结束
if (s.charAt(j) != t.charAt(j)) {
if (count != 0)
break;
count++;
}
}
if (j != s.length() || count != 1)//判断是否遍历到字符串s的最后一位，或者不是恰好改变了一个字符
continue;
adjs.add(t);
}
return adjs;
}
}
发表于 2019-02-18 20:11:54
回复(0)
// 相对于其他答案，这个答案应该是稍微优化一点的版本。
// 理由是 他们在找newword 是否存在于已给字符数组中，用的是遍历，
// 而这个是用的map。。。。
// 还是十分佩服能总结出方法的人。
class Change {
public:
int countChanges(vector<string> dic, int n, string s, string t) {
// write code here
// get a string map first
map<string,int> stringmap;
for (int i = 0 ; i != n ; i ++)
stringmap[dic[i]] = 1;
return BFS(s,t,stringmap);
}
int BFS(string s, string t, map<string,int> &stringmap) {
if (s == t) return 0;
queue<pair<string,int>> q;
q.push(make_pair(s,0));
map<string,int> visited;
visited[s] = 1;
while(!q.empty()) {
pair<string,int> cur = q.front();
q.pop();
for (int i = 0 ; i != cur.first.length(); i++) {
string newword = cur.first;
for (int j = 0 ; j != 26 ; j++) {
newword[i] = 'a' + j;
if (newword == t && stringmap.find(newword) != stringmap.end()) {
return cur.second + 1;
}
if (visited.find(newword) == visited.end() &&
stringmap.find(newword) != stringmap.end()) {
visited[newword] = 1;
q.push(make_pair(newword,cur.second + 1));
}
}
}
}
return -1;
}
};
发表于 2019-02-13 19:57:55
回复(0)
import java.util.*;
/*思路：参考BFS算法，遍历到一个字符串，将该字符串转换一次并且数组中存在的与该字符串不等的字符串入队列
当队列遍历到一层中存在可以转换成目标字符串时跳出循环并将count+1即为结果
*/
public class Change {
public int countChanges(String[] dic, int n, String s, String t) {
Queue<String> queue=new ArrayDeque<String>();
ArrayList<String> list=new ArrayList<String>();//用于标记已访问过的字符，避免重复访问
queue.offer(s);
queue.offer("#");//用于标记层数
int count=0;
boolean res=false;//用于记录是否存在转换
while (!queue.isEmpty()) {
String temp=queue.poll();
if (temp.equals("#")) {//当遍历到“#”时，层数+1即转换操作+1
count++;
temp=queue.poll();
queue.offer("#");
}
list.add(temp);
for (int i = 0; i < dic.length; i++) {
if (temp!=dic[i]&&!list.contains(dic[i])) {
if (isContain(temp, dic[i])) {
if (dic[i].equals(t)) {//判断是否等于目标字符串
res=true;
break;
}
if (!queue.contains(dic[i])) {//满足转换条件的结果可能重复，则去重
queue.offer(dic[i]);
}
}
}
}
if (res) {
break;
}
}
if (res) {
return count+1;
}else {
return -1;
}
}
/*判断一个字符串是否存在一次转换就形成另一个字符串*/
public boolean isContain(String s1,String s2){
boolean res=true;
char[] c1=s1.toCharArray();
char[] c2=s2.toCharArray();
if (s1.length()!=s2.length()) {
return false;
}else {
for (int i = 0; i < c2.length; i++) {
if (c1[i]!=c2[i]) {
c1[i]=c2[i];
if (s2.equals(String.valueOf(c1))) {
break;
}else {
res=false;
break;
}
}
}
return res;
}
}
}
发表于 2018-08-31 10:33:59
回复(0)
总算调好了，基本的bfs运用：
class Change {
public:
int countChanges(const vector<string>& dic, int n, const string& s, const string& t) {
// write code here
if(s==t)return 0;
auto ret=0;
vector<vector<bool>>g(n,vector<bool>(n,false));
vector<bool>visited(n,false);
for(int i=0;i<n;++i){
for(int j=i;j<n;++j)
if(oneDiff(dic[i],dic[j])){
g[i][j]=true;
g[j][i]=true;
}
}
queue<int>q;
auto pos=find(dic.begin(),dic.end(),s)-dic.begin();
q.push(pos);
visited[pos]=true;
while(!q.empty()){
auto n=q.size();
if(n>0)++ret;
for(int i=0;i<n;++i){
auto index=q.front();
q.pop();
auto neighbors=getNeighbor(index,g);
for(auto ele : neighbors){
if(dic[ele]==t)
return ret;
if(visited[ele]==false){
visited[ele]=true;
q.push(ele);
}
}
}
}
return 0;
}
private:
bool oneDiff(const string&s1,const string&s2){
if(s1.size()!=s2.size())return false;
auto count=0;
for(int i=0;i<s1.size();++i)
if(s1[i]!=s2[i])
if(++count==2)
return false;
return count==1;
}
vector<int> getNeighbor(int i,const vector<vector<bool>>&g){
vector<int>ret;
for(int j=0;j<g.size();++j)
if(g[i][j])
ret.push_back(j);
return ret;
}
};
public:
int countChanges(const vector<string>& dic, int n, const string& s, const string& t) {
// write code here
if(s==t)return 0;
auto ret=0;
vector<vector<bool>>g(n,vector<bool>(n,false));
vector<bool>visited(n,false);
for(int i=0;i<n;++i){
for(int j=i;j<n;++j)
if(oneDiff(dic[i],dic[j])){
g[i][j]=true;
g[j][i]=true;
}
}
queue<int>q;
auto pos=find(dic.begin(),dic.end(),s)-dic.begin();
q.push(pos);
visited[pos]=true;
while(!q.empty()){
auto n=q.size();
if(n>0)++ret;
for(int i=0;i<n;++i){
auto index=q.front();
q.pop();
auto neighbors=getNeighbor(index,g);
for(auto ele : neighbors){
if(dic[ele]==t)
return ret;
if(visited[ele]==false){
visited[ele]=true;
q.push(ele);
}
}
}
}
return 0;
}
private:
bool oneDiff(const string&s1,const string&s2){
if(s1.size()!=s2.size())return false;
auto count=0;
for(int i=0;i<s1.size();++i)
if(s1[i]!=s2[i])
if(++count==2)
return false;
return count==1;
}
vector<int> getNeighbor(int i,const vector<vector<bool>>&g){
vector<int>ret;
for(int j=0;j<g.size();++j)
if(g[i][j])
ret.push_back(j);
return ret;
}
};
发表于 2018-07-28 23:27:06
回复(0)
//word ladder,bfs
class Change {
public:
int countChanges(vector<string> dic, int n, string s, string t) {
// write code here
map<string,int> co;
for(int i=0;i<n;i++)
{
if(co.count(dic[i]))
co[dic[i]]++;
else
co[dic[i]]=1;
}
queue<string> tp;
tp.push(s);
int num=1;
int cnt;
int count=0;
bool find=false;
while(!find&&num)
{
cnt=num;
num=0;
while(!find&&cnt--)
{
string cur=tp.front();
tp.pop();
for(int i=0;i<int(cur.length())&&!find;i++)
{
char w=cur[i];
for(char c='a';c<='z';c++)
{
cur[i]=c;
if(cur==t)
{
find=true;
break;
}
else if(co.count(cur))
{
num++;
tp.push(cur);
co[cur]--;
if(co[cur]==0)
co.erase(cur);
}
}
cur[i]=w;
}
}
count++;
}
if(!find)
return -1;
return count;
}
};
发表于 2018-07-02 09:49:42
回复(0)
问题信息
难度：
35条回答
82收藏
22648浏览
通过挑战的用户
查看代码-
2022-08-21 12:31:32
-
2022-07-25 10:04:02
-
2022-06-29 12:16:56 -
2022-06-15 14:15:08 -
2022-06-07 11:58:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class Change { public: int countChanges(vector<string> dic, int n, string s, string t) { vector<string>::iterator ite = find(dic.begin(),dic.end(),s); int result = BFS(s,t,dic); if(ite != dic.end()){ --result; }//if return result; } private: int BFS(string start,string end,vector<string> &dict){ if(start == end){ return 0; }//if // 存放单词和单词所在层次 queue<pair<string,int> > q; q.push(make_pair(start,1)); // 判断是否访问过 vector<string> visited; visited.push_back(start); while(!q.empty()){ pair<string,int> cur = q.front(); q.pop(); string word = cur.first; int size = word.size(); // 穷尽所有可能的变换 for(int i = 0;i < size;++i){ string newWord(word); // 每次只变换一个字符 有26种可能 for(int j = 0;j < 26;++j){ newWord[i] = 'a'+j; // 找到目标返回 if(newWord == end){ return cur.second + 1; }//if // 判断之前访问过或者是否在字典里 vector<string>::iterator ite = find(dict.begin(),dict.end(),newWord); vector<string>::iterator ite2 = find(visited.begin(),visited.end(),newWord); if(ite2 == visited.end() && ite != dict.end()){ visited.push_back(newWord); q.push(make_pair(newWord,cur.second+1)); }//if }//for }//for }//while return -1; } };