Алгоритм поиска слова Java

Question

У меня есть List<List<String>>, где строка представляет собой один символ.

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"
 }
}

Так что я хочу найти слово в этом (то есть "Боб"), и нет никакого установленного размера длядлина списка.Это как поиск слова, поэтому слово может быть в одной строке, разные буквы в разных строках и т. Д. Как бы я сделал это программно?Я почти уверен, что мне придется создать метод и вызвать себя в нем, но я не уверен, как это сделать.Спасибо за ваше время!

Answer 1

Самый простой (не самый эффективный) способ - поиск по первой букве слова.Затем найдите вокруг этого слова вторую букву.Если вы найдете совпадение, продолжайте идти В ЭТОМ НАПРАВЛЕНИИ (логика должна быть легкой для этого.) Остановитесь, когда вы закончите слово, получите неправильную букву или нажмете на край доски.

Лучшая вещьВы можете сделать для себя сам, сделать метод, который возвращает символ (или строку, что угодно) для данной координаты X, Y.Это может сделать что-то вроде этого:

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

Answer 2

Вы также можете искать слово со сложностью O (n) при условии, что вы строите соответствующую внутреннюю структуру данных из вашего List<List<String>>.Вот пример:

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]

Примечания:

• a Position объект идентифицирует list и index в этом списке

• во время строительства я строю Map, где ключи - это символы, а значения - это список Position объектов, каждый из которых говорит мнекакой список и какой индекс в этом списке я могу найти этот символ

• при поиске слова, я просто сканирую символы слова и получаю первые доступные Position для этого символа в моемMap

• вы можете легко изменить метод findWord, чтобы получить все возможные комбинации

• вы можете легко добавить метод для обновления внутреннегоMap с дополнительной строкой в ​​существующем списке или с новыми списками

• сложность: инициализация O (n ^ 2) (необходимо просмотреть список списков строк);найти слово O (n)