使用单词字典将字符串a转换为b

4 回答

• 2

  如何通过一次只更改一个字符并确保所有中间单词都在字典中来将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
  

  回复于 2024-04-27T11:26:34+08:00
• 0

  您可以将此视为图搜索问题 . 每个单词都是图中的一个节点，如果两个单词之间只有一个字母，则它们之间有一条边 . 在此图表上运行BFS将找到起始单词和目标单词之间的最短路径（如果可以将一个单词转换为另一个单词），并且将报告无法执行此操作 .

  回复于 2024-04-27T11:26:34+08:00
• 0

  简单地在图表上做一个BFS，其节点是单词，如果节点上的单词相差一个字母，则两个节点之间有一条边 . 通过这种方式，您可以通过从给定的起始单词启动BFS来提供解决方案 . 如果到达目标节点，则可能，否则不可能 .

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

  P.S：巧合的是，在一次采访中我也问过这个问题，我编写了这个解决方案！

  回复于 2024-04-27T11:26:34+08:00
• 0

  预先构建并重新使用旅行 Map . 例如，使用有效的单词距离构建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);
  }
  

  回复于 2024-04-27T11:26:34+08:00