Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- static public Set<String> baldaSearcher(String inputName, Set<String> words) throws IOException {
- Set<String> set = new HashSet<>();
- String line;
- List<String[]> list = new ArrayList<>();
- try (BufferedReader buffer = new BufferedReader(new FileReader(new File(inputName)))) { // Парсим строку и
- while ((line = buffer.readLine()) != null) list.add(line.split("\\s+")); // добавляем в лист
- }
- int numberOfRows = list.size();
- int numberOfColumns = list.get(0).length;
- char[][] matrix = new char[numberOfRows][numberOfColumns];
- for (int i = 0; i < numberOfRows; i++) { // Заполняем матрицу чарами (буквами) из листа
- for (int j = 0; j < numberOfColumns; j++) { // T=O(i*j)
- matrix[i][j] = list.get(i)[j].charAt(0);
- }
- }
- Cell cell;
- List<Cell> cellList = new ArrayList<>();
- int numberOfLetters = 1;
- for (String word: words) {
- for (int i = 0; i < numberOfRows; i++) {
- for (int j = 0; j < numberOfColumns; j++) {
- if (matrix[i][j] == word.charAt(0)) {
- cell = new Cell(i, j);
- if (cell.wordSearch(word, matrix, numberOfLetters, numberOfRows, numberOfColumns, cellList)) set.add(word);
- numberOfLetters = 1;
- cellList.clear();
- }
- }
- }
- }
- return set;
- }
- }
- class Cell {
- private int row;
- private int column;
- Cell(int rowId, int colId) {
- row = rowId;
- column = colId;
- }
- public boolean inRange(int rowSize, int colSize) {
- return 0 <= row && row < rowSize && 0 <= column && column < colSize;
- }
- public Cell[] getNeighbours(int rowId, int colId) {
- Cell[] surrounding = new Cell[4];
- surrounding[0] = new Cell(-1 + rowId, colId);
- surrounding[1] = new Cell(rowId, 1 + colId);
- surrounding[2] = new Cell(1 + rowId, colId);
- surrounding[3] = new Cell(rowId, -1 + colId);
- return surrounding;
- }
- public boolean wordSearch(String word, char[][] matrix, int numberOfLetters, int width, int high, List<Cell> list) {
- if (numberOfLetters == word.length()) return true;
- numberOfLetters++;
- Cell[] surrounding = this.getNeighbours(row, column);
- for (Cell side: surrounding) {
- if (side.inRange(width, high) && matrix[side.row][side.column] == word.charAt(numberOfLetters - 1)
- && !list.contains(side)) {
- list.add(this);
- if (side.wordSearch(word, matrix, numberOfLetters, width, high, list)) return true;
- }
- }
- return false;
- }
- @Override
- public boolean equals(Object other) {
- if (this == other) return true;
- if (other instanceof Cell) {
- Cell newOther = (Cell) other;
- return row == (newOther.row) && column == newOther.column;
- }
- return false;
- }
- @Override
- public int hashCode() {
- return (row + column) * 55;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement