add word search

resoliwan · resoliwan · commit 7cd2b70875dc · 2022-12-01T09:08:50.000+09:00
diff --git a/leetcode/test_1_14_word_serach.py b/leetcode/test_1_14_word_serach.py
@@ -3,12 +3,8 @@
 # Given an m x n grid of characters board and a string word, return true if word exists in the grid.
 # The word can be constructed from letters of sequentially adjacent cells, where adjacent cells
 # are horizontally or vertically neighboring. The same letter cell may not be used more than once.
-# &#49884;&#44036;&#50640;&#49436; &#50500;&#50883;.
-import copy
 from collections import Counter, namedtuple
-from typing import List, Tuple
-
-FourSide = namedtuple("FourSide", ["east", "south", "north", "west"])
+from typing import List
 
 
 class Solution:
@@ -24,13 +20,13 @@ def is_include_number_of_characters(self, a_word, b_word):
 
         return res
 
-    def exist(self, raw_board: List[List[str]], word: str) -> bool:
+    def exist(self, board: List[List[str]], word: str) -> bool:
         """
         [( A, 0, 0 ), ( B, 0, 1 ), ( C, 1, 0 ), ( D, 1, 1 )]
         res = list
         - &#51116;&#44480;&#47196; &#54396;&#45796;.
             - 4&#48169;&#50640; &#50630;&#51004;&#47732; &#47532;&#53556;
-                - &#54620;&#48264; &#49324;&#50857;&#54620; &#44163;&#51008; 4&#48169; &#52286;&#51012; &#46412; &#50504;&#45208;&#50724;&#44172; &#51228;&#50557;
+                - &#54620;&#48264; &#49324;&#50857;&#54620; &#44163;&#51008; &#54032;&#51012; &#48320;&#44221;&#54620;&#45796;.
         1. &#49884;&#51089;&#51216;&#51012; &#52286;&#45716;&#45796;.
             &#44033; &#49884;&#51089;&#51216; &#49692;&#49436;&#47196;
         2. 4&#48169;&#50640; &#45796;&#51020;&#51012; &#52286;&#45716;&#45796;.
@@ -39,134 +35,55 @@ def exist(self, raw_board: List[List[str]], word: str) -> bool:
             [&#48513;, &#49436;, &#45224;, &#46041;]
             -> [[]]
         3. &#46112;&#46412;&#44620;&#51648; &#52286;&#45716;&#45796;.
-        """
-        if not self.is_include_number_of_characters(
-            "".join(["".join(row) for row in raw_board]), word
-        ):
-            return False
-
-        res = list()
-        board = self.get_point_board(raw_board)
-        for row in board:
-            for point in [p for p in row if p[0] == word[0]]:
-                res.append(point)
-                self.append_next_point(1, point, res, word, board)
-
-                if self.get_word(res) == word:
-                    return True
-                else:
-                    res = list()
-
-        return self.get_word(res) == word
-
-    def get_word(self, res):
-        return "".join([ele[0] for ele in res])
-
-    def append_next_point(
-        self,
-        next_idx: int,
-        point: List,
-        res: List,
-        word: str,
-        board: List[List],
-    ) -> None:
-        if next_idx >= len(word):
-            return
-
-        len_original_res = len(res)
-        sides = [s for s in self.get4side(board, point) if s is not None]
-        for side in [side for side in sides if side[0] == word[next_idx]]:
-            if side in res:
-                continue
-
-            res.append(side)
-            self.append_next_point(next_idx + 1, side, res, word, board)
-
-            if self.get_word(res) == word:
-                break
-            else:
-                while len_original_res < len(res):
-                    res.pop()
-
-    def get4side(self, board: List[List], point: List):
-        north = self.get_point(board, ("", point[1] - 1, point[2] + 0))
-        west = self.get_point(board, ("", point[1] + 0, point[2] - 1))
-        south = self.get_point(board, ("", point[1] + 1, point[2] + 0))
-        east = self.get_point(board, ("", point[1] + 0, point[2] + 1))
 
-        return FourSide(
-            east,
-            south,
-            north,
-            west,
-        )
 
-    def get_point(self, board, point):
-        if point[1] < 0 or point[2] < 0:
-            return None
+        1. &#48372;&#46300; &#48176;&#50676;&#51032; &#47784;&#46304; &#50836;&#49548;&#47484; &#49692;&#54924;&#54620;&#45796;.
+        2. word[0]&#44284; board[x][y]&#50836;&#49548;&#44032; &#44057;&#45796;&#47732;
+            - &#51116;&#44480;&#54840;&#52636;
 
-        result = None
-        try:
-            result = board[point[1]][point[2]]
-        except IndexError:
-            result = None
+            - x, y&#44032; &#48372;&#46300;&#47484; &#48279;&#50612;&#45208;&#45716;&#51648; &#54869;&#51064;
+            - word[i]&#50752; board[x][y]&#44032; &#44057;&#51008;&#51648; &#54869;&#51064;
+                - &#44057;&#45796;&#47732; &#48169;&#47928;&#54664;&#45796;&#45716; &#54364;&#49884;&#47196; board[x][y]&#51032; . &#47484; &#48320;&#44221;.
+            - board[x-1][y]&#50752; &#45796;&#51020; &#47928;&#51088;&#47196; &#54840;&#52636;
+            - board[x+1][y]&#50752; &#45796;&#51020; &#47928;&#51088;&#47196; &#54840;&#52636;
+            - board[x][y-1]&#50752; &#45796;&#51020; &#47928;&#51088;&#47196; &#54840;&#52636;
+            - board[x][y2+]&#50752; &#45796;&#51020; &#47928;&#51088;&#47196; &#54840;&#52636;
 
-        return result
 
-    def get_point_board(self, raw_board):
-        board = [[] for _ in range(len(raw_board))]
-        for row_i, row in enumerate(raw_board):
-            for col_i, col in enumerate(row):
-                board[row_i].append((col, row_i, col_i))
+        """
+        if not self.is_include_number_of_characters(
+            "".join(["".join(row) for row in board]), word
+        ):
+            return False
 
-        return board
+        for x, row in enumerate(board):
+            for y, col in enumerate(row):
+                if col == word[0] and self.is_word_exist(x, y, word, board):
+                    return True
 
+        return False
 
-def test_get_4_side():
-    t0 = dict(
-        board=[["A", "B"], ["C", "D"]],
-        word="AB",
-        output=True,
-    )
-    s = Solution()
-    board = s.get_point_board(t0["board"])
-    sides = s.get4side(board, ("A", 0, 0))
-    assert sides.north is None
-    assert sides.west is None
-    assert sides.south == ("C", 1, 0)
-    assert sides.east == ("B", 0, 1)
+    def is_word_exist(self, x, y, word, board):
+        if x < 0 or x >= len(board) or y < 0 or y >= len(board[x]):
+            return False
 
-    sides = s.get4side(board, ("D", 1, 1))
-    assert sides.north == ("B", 0, 1)
-    assert sides.west == ("C", 1, 0)
-    assert sides.south is None
-    assert sides.east is None
+        if word[0] != board[x][y]:
+            return False
 
+        if len(word) == 1:
+            return True
 
-def test_get_point_board():
-    t0 = dict(
-        board=[["A", "B"], ["C", "D"]],
-        word="AB",
-        output=True,
-    )
-    s = Solution()
+        board[x][y] = "."
 
-    board = s.get_point_board(t0["board"])
-    assert board == [[("A", 0, 0), ("B", 0, 1)], [("C", 1, 0), ("D", 1, 1)]]
+        for next_x, next_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
+            if self.is_word_exist(next_x, next_y, word[1:], board):
+                return True
 
+        board[x][y] = word[0]
+        return False
 
-def test_get_point():
-    t0 = dict(
-        board=[["A", "B"], ["C", "D"], []],
-        word="AB",
-        output=True,
-    )
-    s = Solution()
-    board = s.get_point_board(t0["board"])
-    a = s.get_point(board, ("", 0, 0))
-    assert a == ("A", 0, 0)
-    e = s.get_point(board, ("", 2, 2))
-    assert e is None
+    def get_word(self, res):
+        return "".join([ele[0] for ele in res])
 
 
 def test_simple_exist():
@@ -192,8 +109,8 @@ def test_simple_exist():
     )
 
     s = Solution()
-    # ts = [t0, t1, t2, t3]
-    ts = [t3]
+    ts = [t0, t1, t2, t3]
+    # ts = [t1]
     for t in ts:
         print(t)
         assert s.exist(t["board"], t["word"]) == t["output"]
