Java字搜索算法

我有一個List<List<String>>其中字符串是單個字符。Java字搜索算法

List { 
List { 
    |"r","x","f","b","e","a","r" 
} 
List { 
    |"a","r","q","b","o","y","t" 
} 
List { 
    |"s","q","z","b","s","b","r" 
} 
}

所以我想在這裏找到一個單詞（即「bob」），並且沒有設置列表長度的大小。這就像是一個詞的搜索，所以這個詞可以在同一行，在不同的行上不同的字母，等等。我將如何編程？我非常肯定，我將不得不做一個方法，並在方法中自己調用，但我不知道如何做到這一點。謝謝你的時間！

來源

2011-05-04 JavaIsGreat

這是一個語法錯誤。如果是僞代碼符號，請解釋'|'是什麼意思？ – delnan 2011-05-04 21:32:22

你的意思是這個清單列表代表了一個字母網格，就像你在超市中的小報和女性雜誌之間的那些單詞搜索問題書一樣？ – sigfpe 2011-05-04 21:34:17

「等」留下了一些重要的細節。我們是否從外部'List'中假設內部'List'的順序是重要的？據推測，這個詞的連續字母必須出現在相同或相鄰的子列表中;但相對的訂單可能會扭轉嗎？同樣，我們是否假定內部'List'中的字母順序也很重要？ – eggyal 2011-05-04 21:36:48

最簡單的（不是最有效的）方法是搜索單詞的第一個字母。然後在第二個字母旁邊搜索那個單詞。如果你找到一個匹配，繼續進入IN THAT DIRECTION（邏輯應該很容易）停止當你完成單詞，得到一個錯誤的字母，或擊中董事會的邊緣。

你可以爲自己做的最好的事情就是爲一個給定的X，Y座標返回一個字符（或一個字符串，無論）。它可能做這樣的事情：

char charAt(int x, int y) { 
    return list.get(x).get(y).charAt(0); 
}

來源

2011-05-04 21:32:59 corsiKa

我唯一要添加到這個答案的是，當你「搜索」和「繼續」時，你需要測試邊緣去」。 – 2011-05-05 01:56:31

@Ted Hopp - 第一段，最後一句，最後一句「或擊中板的邊緣。」 :-) – corsiKa 2011-05-05 02:49:23

你說的對。我正在考慮「搜索周圍」部分 - 它似乎只適用於「繼續前進」的部分。 – 2011-05-05 05:46:02

也可以搜索與提供您從List<List<String>>構建一個適當的內部數據結構爲O（n）複雜的詞。這裏有一個例子：

public class SO5890087 { 

    Map<Character, List<Position>> pmaps = 
     new HashMap<Character, List<Position>>(); 

    public static void main(String[] args) { 
     String[][] strings = new String[][] { 
       { "r", "x", "f", "b", "e", "a", "r" }, 
       { "a", "r", "q", "b", "o", "y", "t" }, 
       { "s", "q", "z", "b", "s", "b", "r" } }; 
     List<List<String>> sss = new ArrayList<List<String>>(); 
     for (int i = 0; i < strings.length; i++) 
      sss.add(new ArrayList<String>(Arrays.asList(strings[i]))); 
     SO5890087 finder = new SO5890087(sss); 
     List<Position> positions = finder.findWord("bob"); 
     for (Position position : positions) 
      System.out.println(position); 
    } 

    public SO5890087(List<List<String>> sss) { 
     for (int i = 0; i < sss.size(); i++) { 
      List<String> ss = sss.get(i); 
      for (int j = 0; j < ss.size(); j++) { 
       Character c = ss.get(j).charAt(0); 
       if (! pmaps.containsKey(c)) 
        pmaps.put(c, new ArrayList<Position>()); 
       pmaps.get(c).add(new Position(i, j)); 
      } 
     } 
    } 

    public List<Position> findWord(String word) { 
     List<Position> result = new ArrayList<Position>(); 
     char[] cs = word.toCharArray(); 
     for (int i = 0; i < cs.length; i++) { 
      if (pmaps.containsKey(cs[i])) { 
       result.add(pmaps.get(cs[i]).get(0)); 
      } 
      else { 
       result.clear(); 
       break; 
      } 
     } 
     return result; 
    } 

    class Position { 
     int list; 
     int index; 

     public Position(int list, int index) { 
      this.list = list; 
      this.index = index; 
     } 

     public int getList() { 
      return list; 
     } 

     public int getIndex() { 
      return index; 
     } 

     @Override 
     public String toString() { 
      return "Position [list=" + list + ", index=" + index + "]"; 
     } 

    } 

}

輸出爲"bob"：

Position [list=0, index=3] 
Position [list=1, index=4] 
Position [list=0, index=3]

注：

一個Position對象識別list，並在該列表中
在施工的index Ť IME我建立一個Map鍵進行字符和值Position對象的列表，每個告訴我，在列表中，並且指數在該列表中查找單詞的時候我能找到該字符
，我只是掃描單詞字符和檢索該字符的第一個可用Position我Map
您可以輕鬆地修改findWord方法返回所有可能的組合
，你可以輕鬆地添加方法來更新內部Map機智h現有列表中的附加字符串或新列表
複雜度：初始化爲O（n^2）（必須掃描字符串列表的列表）。找到一個字是O（n）

來源

2011-05-05 09:02:14 MarcoS

Java字搜索算法

回答

相關問題