4

你有一个单词字典和两个字符串a和b.

如何通过一次只更改一个字符并确保所有中间词都在字典中来将 a 转换为 b？

例子：

dictionary: {"cat", "bat", "hat", "bad", "had"}
a = "bat"
b = "had"

解决方案：

"bat" -> "bad" -> "had"

编辑：下面给出的解决方案建议从字典单词中构建一个图表，这样每个单词都将具有与所有其他单词相差一个字符的边缘。如果字典太大，这可能会有些困难（假设我们不仅仅是在谈论英语单词）。

此外，即使这是可以接受的，创建这样一个图的最佳算法是什么？从一个单词到所有其他单词的边缘查找将是 O(n)，其中 n 是字典大小。总图的构造将是 O(n2)？有更好的算法吗？

这不是作业问题，而是面试问题。

4

4 回答 4

2

您可以将其视为图形搜索问题。每个单词都是图中的一个节点，如果两个单词相差一个字母，则它们之间存在一条边。在此图上运行BFS将找到起始词和目标词之间的最短路径（如果可以将一个词转换为另一个词），并且将报告没有其他方法可以做到这一点。

于 2013-07-07T18:29:53.970 回答
0

只需在节点为单词的图上进行 BFS，并且如果节点上的单词相差一个字母，则两个节点之间有一条边。这样，您可以通过从给定的起始字开始 BFS 来提供解决方案。如果您到达目标节点，那么它是可能的，否则不是。

您还可以提供所采取的步骤，并注意您将提供最少的步骤来获得所需的奖励。

PS：巧合的是，在一次采访中也向我提出了这个问题，我编写了这个解决方案！

于 2013-07-07T18:35:03.523 回答
0

如何通过一次只更改一个字符并确保所有中间词都在字典中来将 a 转换为 b？

这是直O(nm)

其中n是字典中的单词m数，是输入单词中的字符数

该算法很简单，如果字典中的单词与输入不匹配 1 个字符，则认为这是一个解决方案：

FOR EACH WORD W IN DICTIONARY DO

    IF SIZE(W) = SIZE(INPUT) THEN

        MIS = 0

        FOR i: 1..SIZE(INPUT) IF W[i] != INPUT[i] THEN MIS = MIS + 1

        IF MIS = 1 THEN SOLUTION.ADD(W)

    END-IF

END-FOR
于 2013-07-08T09:16:18.230 回答
0

预先构建和重复使用旅行地图。例如，构建一个具有有效单词距离的 scity[][]，可以重复使用。

只是一个求职的快速练习，可能会被简化。

#define SLEN 10
char* dict[SLEN]={
"bat",
"hat",
"bad",
"had",
"mad",
"tad",
"het",
"hep",
"hady",
"bap"};

int minD=0xfffff;
int edst(char *a, char *b)
{
 char *ip=a,*op=b;
 int d=0;
 while((*ip)&&(*op))
  if(*ip++!=*op++) 
  {
   if(d) return 0;
   d++;
  }
 if((*op)||(*ip)) d++;
 return d;
}
int strlen(char *a)
{
 char *ip=a;
 int i=0;
 while(*ip++)
  i++;
 return i;
}
int valid(char *dict[], int a, int b)
{
 if((a==b)||(strlen(dict[a])!=strlen(dict[b]))||(edst(dict[a],dict[b])!=1)) return 0;
 return 1;
}

void sroute(int scity[SLEN][SLEN], char* dict[], int a[], int end, int pos)
{
 int i,j,d=0;
 if(a[pos]==end)
 {
  for(i=pos;i<(SLEN-1);i++)
  {
   printf("%s ",dict[a[i]]);
   d+=scity[a[i]][a[i+1]];
  }
  printf(" %s=%d\n",dict[a[SLEN-1]],d);
  if(d<minD) minD=d;
  return;
 }

 for(i=pos-2;i>=0;i--)
 {
  int b[SLEN];
  for(j=0;j<SLEN;j++) b[j]=a[j];
  b[pos-1]=a[i];
  b[i]=a[pos-1];
  if(scity[b[pos-1]][b[pos]]==1)
    sroute(scity,dict,b,end,pos-1);
 }
 if(scity[a[pos-1]][a[pos]]==1) sroute(scity,dict,a,end,pos-1);
}

void initS(int scity[SLEN][SLEN], char* dict[], int a, int b)
{
 int i,j;
 int c[SLEN];
 for(i=0;i<SLEN;i++)
  for(j=0;j<SLEN;j++)
   scity[i][j]=valid(dict,i,j);
 for(i=0;i<SLEN;i++) c[i]=i;
 c[SLEN-1]=b;
 c[b]=SLEN-1;

 sroute(scity, dict, c, a, SLEN-1);
 printf("min=%d\n",minD);
}
于 2016-11-14T23:00:50.817 回答