Python solution with precheck to accelerate

  • 1

    my python solution with precheck to eliminate most cases

    # coding=utf-8
    class Solution:
        # @param {character[][]} board
        # @param {string} word
        # @return {boolean}
        def exist(self, board, word):
            if not self.preCheck(board, word):
                return False
            self.lenY, self.lenX = len(board), len(board[0])
            self.used = {}
            self.board = board
            self.found = False
            for y, line in enumerate(board):
                for x, char in enumerate(line):
                    if char == word[0]:
                        self.used[(x,y)] = True
              , (x, y), 0, word)
                        self.used[(x,y)] = False
                        if self.found:
                            return True
            return False
        def preCheck(self, board, word):
            '''to see if there are enough char num in the board,if not, there's no need to search'''
            # char -> char's num in the board
            availableCharNumMap = {}
            # char -> char's num in the word
            neededCharNumMap = {}
            def fillMapWithLine(m, ones):
                for one in ones:
                    if one in m:
                        m[one] += 1
                        m[one] = 1
            for line in board:
                fillMapWithLine(availableCharNumMap, line)
            fillMapWithLine(neededCharNumMap, word)
            for char, num in neededCharNumMap.items():
                ok = char in availableCharNumMap and availableCharNumMap.get(char) >= num
                if not ok:
                    return False
            return True
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        def validPos(self, pos, char):
            x, y = pos
            if not self.found \
                    and 0 <= x and x < self.lenX \
                    and 0 <= y and y < self.lenY \
                    and not self.used.get(pos) is True \
                    and char == self.board[y][x]:
                return True
                return False
        def search(self, board, pos, index, word):
            if index == len(word) - 1:
                self.found = True
                return True
            for direction in Solution.directions:
                newX, newY = (pos[0] + direction[0], pos[1] + direction[1])
                newPos = (newX, newY)
                char = word[index + 1]
                if self.validPos(newPos, char):
                    self.used[newPos] = True
          , newPos, index + 1, word)
                    self.used[newPos] = False
    import unittest
    class SolutionTest(unittest.TestCase):
        def setUp(self):
            self.s = Solution()
        def testExist(self):
            board = ["ABCE",
            assert self.s.exist(board, "ABCCED") == True
            assert self.s.exist(board, "SEE") == True
            assert self.s.exist(board, "ABCB") == False
            assert self.s.exist(["aa"], "aaa") == False
            assert self.s.exist(["aaaa","aaaa","aaaa","aaaa","aaab"], "aaaaaaaaaaaaaaaaaaaa") == False
            print self.s.exist(["a"], "a")
        def testPreCheck(self):
            assert self.s.preCheck(["aaaa","aaaa","aaaa","aaaa","aaab"], "aaaaaaaaaaaaaaaaaaaa") == False

  • 0

    This is a great idea to improve performance. However, the preCheck function can be optimized. No need to use two dictionaries for it. One should be enough. Below is my version with running time 80~90 ms.
    The _hasEnoughCharacters function does the same job as preCheck

    from collections import defaultdict
    class Solution:
        # @param {character[][]} board
        # @param {string} word
        # @return {boolean}
        def exist(self, board, word):
            def _hasEnoughCharacters(board, word):
                characterCounts = defaultdict(int)
                for ch in word:
                    characterCounts[ch] += 1
                return all(sum(map(lambda line : line.count(ch), board)) >= count for ch, count in characterCounts.items())
            def _exist(board, used, x, y, rowNum, colNum, word, start, end):
                if start >= end:
                    # done
                    return True
                # check left, right, up down
                for i in range(4):
                    x += dx[i]
                    y += dy[i]
                    if 0 <= x < rowNum and 0 <= y < colNum and board[x][y] == word[start] and not used[x][y]:
                        used[x][y] = True
                        ans = _exist(board, used, x, y, rowNum, colNum, word, start+1, end)
                        if ans:
                            return ans
                        used[x][y] = False
                return False
            if _hasEnoughCharacters(board, word):
                rowNum, colNum, wordLen = len(board), len(board[0]), len(word)
                used = [[False] * colNum for _ in range(rowNum)]
                dx, dy = [-1, 2, -1, 0], [ 0, 0, -1, 2]
                # start from every position containing the first character in word
                for x in range(rowNum):
                    for y in range(colNum):
                        if board[x][y] == word[0]:
                            used[x][y] = True
                            ans = _exist(board, used, x, y, rowNum, colNum, word, 1, wordLen)
                            if ans:
                                return True
                            used[x][y] = False
            return False

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.