Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.24 KB | None | 0 0
  1. static public Set<String> baldaSearcher(String inputName, Set<String> words) throws IOException {
  2. Set<String> set = new HashSet<>();
  3. String line;
  4. List<String[]> list = new ArrayList<>();
  5.  
  6. try (BufferedReader buffer = new BufferedReader(new FileReader(new File(inputName)))) { // Парсим строку и
  7. while ((line = buffer.readLine()) != null) list.add(line.split("\\s+")); // добавляем в лист
  8. }
  9.  
  10. int numberOfRows = list.size();
  11. int numberOfColumns = list.get(0).length;
  12. char[][] matrix = new char[numberOfRows][numberOfColumns];
  13. for (int i = 0; i < numberOfRows; i++) { // Заполняем матрицу чарами (буквами) из листа
  14. for (int j = 0; j < numberOfColumns; j++) { // T=O(i*j)
  15. matrix[i][j] = list.get(i)[j].charAt(0);
  16. }
  17. }
  18.  
  19. Cell cell;
  20. List<Cell> cellList = new ArrayList<>();
  21. int numberOfLetters = 1;
  22. for (String word: words) {
  23. for (int i = 0; i < numberOfRows; i++) {
  24. for (int j = 0; j < numberOfColumns; j++) {
  25. if (matrix[i][j] == word.charAt(0)) {
  26. cell = new Cell(i, j);
  27. if (cell.wordSearch(word, matrix, numberOfLetters, numberOfRows, numberOfColumns, cellList)) set.add(word);
  28. numberOfLetters = 1;
  29. cellList.clear();
  30. }
  31. }
  32. }
  33. }
  34. return set;
  35. }
  36. }
  37.  
  38. class Cell {
  39.  
  40. private int row;
  41. private int column;
  42.  
  43. Cell(int rowId, int colId) {
  44. row = rowId;
  45. column = colId;
  46. }
  47.  
  48. public boolean inRange(int rowSize, int colSize) {
  49. return 0 <= row && row < rowSize && 0 <= column && column < colSize;
  50. }
  51.  
  52. public Cell[] getNeighbours(int rowId, int colId) {
  53. Cell[] surrounding = new Cell[4];
  54. surrounding[0] = new Cell(-1 + rowId, colId);
  55. surrounding[1] = new Cell(rowId, 1 + colId);
  56. surrounding[2] = new Cell(1 + rowId, colId);
  57. surrounding[3] = new Cell(rowId, -1 + colId);
  58. return surrounding;
  59. }
  60.  
  61. public boolean wordSearch(String word, char[][] matrix, int numberOfLetters, int width, int high, List<Cell> list) {
  62. if (numberOfLetters == word.length()) return true;
  63. numberOfLetters++;
  64. Cell[] surrounding = this.getNeighbours(row, column);
  65. for (Cell side: surrounding) {
  66. if (side.inRange(width, high) && matrix[side.row][side.column] == word.charAt(numberOfLetters - 1)
  67. && !list.contains(side)) {
  68. list.add(this);
  69. if (side.wordSearch(word, matrix, numberOfLetters, width, high, list)) return true;
  70. }
  71. }
  72. return false;
  73. }
  74.  
  75. @Override
  76. public boolean equals(Object other) {
  77. if (this == other) return true;
  78. if (other instanceof Cell) {
  79. Cell newOther = (Cell) other;
  80. return row == (newOther.row) && column == newOther.column;
  81. }
  82. return false;
  83. }
  84.  
  85. @Override
  86. public int hashCode() {
  87. return (row + column) * 55;
  88. }
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement