來自Java中char數組的字符串的所有可能組合

我有一個Java學校項目，我也被分配了。現在我遇到了一個我無法弄清楚的項目問題。應用程序必須從二維字符數組（char [] []板）生成所有可能的字組合（可通過字典進行驗證）。該板是動態的，因爲用戶可以選擇比例尺：4x4,5x5,4x5,5x4,4x6，...所以我想嵌套循環不會在這裏適用，糾正我，如果我錯了。單詞必須水平，垂直和對角地生成。 4x4板的示例：來自Java中char數組的字符串的所有可能組合

| u | a | u | s |

| n | n |我|我|

| a | o | e | b |

| e | u | e | z |

Code was completely wrong.

另一個想法可能是蠻力在黑板上每一個可能的路徑，然後嘗試那些保存路徑，以驗證它是否是一個詞或沒有。

在此先感謝！

來源

2013-01-20 user1929899

你是什麼意思與「在板上產生的話」？你的輸入是什麼，它的輸出是什麼？ – meriton

該應用程序在隨機基礎上（隨機字符）生成板，然後必須在多個方向上（水平，垂直和對角線）找到板上所有可能的單詞，並且可能不會訪問兩次角色。 – user1929899

「多個方向」是什麼意思？單個單詞可以使用多個方向，即單詞必須是直線還是曲線可以在整個板上？ – meriton

一種方法是：

for each path on the board 
    if corresponding word in dictionary 
     print it

要找到所有的路徑，你可以適應任何graph traversal algorithm。

現在這將會非常緩慢，因爲有一個大小很大的板子的路徑（對於有n個單元的板子，我們最多可以有n * 4^(n - 1)路徑，所以對於5x5板子，有一些像25 * 2^50 = = 10^16路徑

改進的一種方法是交叉遍歷圖和檢查字典，如果當前路徑的單詞不是字典單詞的前綴，則中止：。

class Board { 

    char[][] ch; 
    boolean[][] visited; 

    Trie dictionary; 

    void find() { 
     StringBuilder prefix = new StringBuilder(); 
     for (int x = 0; x < maxx; x++) { 
      for (int y = 0; y < maxy; y++) { 
       walk(x, y, prefix); 
      } 
     } 
    } 

    void walk(int x, int y, StringBuilder prefix) { 
     if (!visited[x][y]) { 
      visited[x][y] = true; 
      prefix.append(ch[x][y]); 

      if (dictionary.hasPrefix(prefix)) { 
       if (dictionary.contains(prefix)) { 
        System.out.println(prefix); 
       } 

       int firstX = Math.max(0, x - 1); 
       int lastX = Math.min(maxx, x + 1); 
       int firstY = Math.max(0, y - 1); 
       int lastY = Math.min(maxy, y + 1); 
       for (int ax = firstX; ax <= lastX; ax++) { 
        for (int ay = firstY; ay <= lastY; ay++) { 
         walk(ax, ay, prefix); 
        } 
       } 
      } 

      prefix.setLength(prefix.length() - 1); 
      visited[x][y] = false; 
     } 
    }

正如你所看到的，方法調用散步本身這種技術被稱爲recursion

這就爲尋找支持有效前綴查詢的字典的數據結構留下了一個問題。最好的這種數據結構是Trie。唉，JDK不包含實現，但幸運的是，編寫一個並不難。

注意：此答案中的代碼尚未經過測試。

來源

2013-01-20 22:22:00 meriton

我現在有一個有點類似的遞歸方法：private void findWord（Woord woord，int positionInWord，Point currentPosition，HashSet visited，StringBuilder currentWoord）{...}，它有效，但有時會給出一些不尋常的結果，沒有連接等... – user1929899

一個相當簡單的概念化方法是對每個位置應用一個breadth-first search（BFS）方法（或深度優先，這取決於您以後可能需要做哪些調整）。這將爲您提供所有可能的字母組合，最多可達到與搜索的最大深度相同的字符級別。根據您的要求，例如最長允許的字數，最長運行時間以及通過數據結構或文件提供字典，這可能是關鍵部分。

或者，您可能需要優化更多。如果是這樣，考慮如何加快BFS或DFS。如果你做了一個DFS，但是知道三個字符，那麼沒有一個字以「zzz」開始？你不需要遍歷所有可能的順序就可以減少很多時間。要有效查看單詞，可能需要進一步調整。但是我首先介紹Java的內置功能（在這個例子中想到了String.startsWith（）），測量性能（可能有限的最大字長），然後優化何時何地需要它。要解決這個

來源

2013-01-20 19:01:04

首先使用簡單的重複方法將行，列和對角線轉換爲字符串。然後，我將它變成一個StringBuilder，或者爲了檢查哪些單詞是真實的，並消除那些不直接來自StringBuilder的單詞。然後，只需將其打印到一個String.There有很多有用的工具來消除或替換java中的單詞。

來源

2015-03-10 12:02:31 Azerogg

來自Java中char數組的字符串的所有可能組合

回答

相關問題