使用單詞字典將字符串a轉換爲b

您有單詞和兩個字符串字典a和b。使用單詞字典將字符串a轉換爲b

如何通過一次只更改一個字符並確保所有中間單詞都在字典中來將a轉換爲b？

實施例：

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

溶液：

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

編輯：下面給出的解決方案，提出構建從詞典詞語的曲線圖，使得每個字將具有邊緣的所有其他詞相差僅一個字符。如果詞典太大了（讓我們說我們不是隻談論英語單詞），這可能有些困難。

此外，即使這是可以接受的，創建這樣的圖的最佳算法是什麼？從一個單詞到所有其他單詞的邊緣都是O（n），其中n是字典大小。總圖構建將是O（n2）？任何更好的算法？

這不是家庭作業問題，而是面試問題。

來源

2013-07-07 user2250246

如果圖形太大而無法在內存中建立，請考慮在每條邊上使用一行數據庫。 –

您可以將此視爲圖搜索問題。每個單詞都是圖中的一個節點，如果兩個單詞相差一個字母，則兩個單詞之間存在一個邊。在此圖上運行BFS將找到起始單詞和目標單詞之間的最短路徑（如果可以將一個單詞轉換爲另一個單詞）並報告沒有辦法做到這一點。

來源

2013-07-07 18:29:53 templatetypedef

但是，如果字典太大以至於難以構造這個圖，那麼你如何解決這個問題呢？另外，你如何從字典中構建上述圖形？你會用什麼數據結構？以及用什麼算法來填充這個圖表？ – user2250246

如果字典非常大，您將從使用A *（星號搜索）而不是BFS中受益。另外，對於一本非常大的詞典，您可能不想預先構建圖表（當然，這裏我們所討論的詞典不僅包含「大約一百萬英語單詞」http://www.slate.com /articles/life/the_good_word/2006/04/word_count.html）。由於圖中的節點太多，您可能需要即時確定圖的合法邊緣（這將需要更多處理）。當你到達節點「帽子」時，你開始檢查「aat」，「bat」，...，「hbt」，以查找邊緣。 – Xantix

也許你可以記住在探索時計算出的邊緣，所以你不必每次重新計算它們就可以重新計算它們。另外，您需要避免返回到已經訪問過的節點，因此請跟蹤訪問的節點。 – Xantix

只需在圖上做一個BFS，其節點就是單詞，如果節點上的單詞相差一個字母，那麼兩個節點之間就存在一條邊。通過這種方式，您可以通過從給定的開始詞開始BFS來提供解決方案。如果你到達目的地節點，那麼它是可能的，否則不是。

您也可以提供所採取的步驟，請注意，您將提供最少的步驟來獲得所需的獎勵。

P.S .:這個問題在接受採訪時也被問到了，我編了這個解決方案！

來源

2013-07-07 18:35:03 Sankalp

但是，如果字典太大以至於構造此圖的難度會很大，那麼你如何解決這個問題呢？ – user2250246

@ user2250246如果字典太大，可以使用hashmap。假設你將字典存儲在一個文件中。將字典的散列圖存儲在單獨的文件中，然後從單詞'a'開始遞歸。繼續在訪問過的散列表中標記單詞，最後到達所需的單詞。 – Sankalp

@ user2250246如果您有任何理解上述問題，那麼我可以在我的答案中解釋它。 – Sankalp

如何將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-08 09:16:18

預先構建和重新使用拉威爾地圖。例如，使用有效的單詞距離構建一個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-14 23:00:50

使用單詞字典將字符串a轉換爲b

回答

相關問題