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字搜索算法

回答

相关问题