我給了一個開始詞,一個目標詞和一個允許使用的詞的字符串數組。我應該使用遞歸來返回是否可以使用給定字符串數組中的至少一個單詞在第一個單詞和最後一個單詞之間構建一個單詞梯形圖。鑑於一串文字,你能構建一個詞語嗎?
遞歸對我來說非常具有挑戰性,所以我對於如何解決這個問題感到迷茫/迷惑。
我給了一個開始詞,一個目標詞和一個允許使用的詞的字符串數組。我應該使用遞歸來返回是否可以使用給定字符串數組中的至少一個單詞在第一個單詞和最後一個單詞之間構建一個單詞梯形圖。鑑於一串文字,你能構建一個詞語嗎?
遞歸對我來說非常具有挑戰性,所以我對於如何解決這個問題感到迷茫/迷惑。
對於每個單詞鏈接到所有可能的兄弟姐妹列表。然後從第一個開始,開始構建所有可能的梯子樹。如果你擊中目標,則返回兩者之間的路徑。您可以在導航樹時使用遞歸。
好的,非常感謝! – 2013-02-23 21:55:40
遞歸包括從內部調用一個函數。你總是需要指定一個退出條件(否則你會得到一個堆棧溢出)。其餘取決於您的需求:
class Myclass {
public static int doSomething(int a) {
if (a < 10) {
doSomething(a + 1);
}
}
public static void main(String [] args) {
System.out.printl(Myclass.doSomething(0));
}
}
好吧抱歉,我不清楚,我知道遞歸是什麼,我只是真的很糟糕,並感到困惑。 – 2013-02-23 21:53:15
What @ user2103249說。對於這樣的事情,你的遞歸例程應該可能返回成功的路徑。東西的秩序:
public String[] canFindPath(String[] pathSoFar) {
for (characters in last word of pathSoFar) {
for (all possible modifications of the character) {
if (modifying the character produces a word in the word list but not already in pathSoFar) {
Create new pathSoFar copy, with the one additional word;
if (additionalWord == goalWord) {
return newPathSoFar;
}
String[] result = canFindPath(newPathSofar);
if (result != null) return result;
}
}
}
return null;
}
雖然有十幾種不同的方法。
最初在單詞列表中構造可能從單詞A到單詞B的轉換的映射會加快速度,因爲您可以通過可能性快速索引而不必在每個步驟中搜索每個單詞。
作業標籤已過時,不應再使用。如果這是一個好問題,不需要這個標籤。如果這是一個不好的問題,編輯它以使其成爲一個好問題。 – Burkhard 2013-02-23 21:39:16
只是刪除標籤是不夠的。我認爲...... – Burkhard 2013-02-23 21:41:09
好吧,也許你應該閱讀[遞歸](https://en.wikipedia.org/wiki/Recursion)是什麼。 – Thomas 2013-02-23 21:41:46