2707. 字符串中的额外字符

2707. 字符串中的额外字符

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        dictionary = set(dictionary)
        dp = [0 for i in range(len(s) + 1)]
        for i in range(1, len(s) + 1):
            dp[i] = dp[i - 1] + 1
            for j in range(i - 1, -1, -1):
                if s[j:i] in dictionary:
                    dp[i] = min(dp[i], dp[j])
        return dp[-1]

841. 钥匙和房间

841. 钥匙和房间

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        need_enter = {i for i in range(len(rooms))}
        have_keys = {0}
        while have_keys:
            key = have_keys.pop()
            if key in need_enter:
                need_enter.discard(key)
                have_keys.update(set(rooms[key]))
        return not bool(need_enter)

1261. 在受污染的二叉树中查找元素

1261. 在受污染的二叉树中查找元素

from typing import List, Optional
from tools import treeGenerate
import json


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque
class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        root.val = 0
        self.root = self.recover(root)

    def recover(self, node: Optional[TreeNode]):
        if node.left:
            node.left.val = 2 * node.val + 1
            self.recover(node.left)
        if node.right:
            node.right.val = 2 * node.val + 2
            self.recover(node.right)
        return node

    def find(self, target: int) -> bool:
        path = deque()
        while target != 0:
            path.appendleft(target)
            target = (target - 1) // 2
        node = self.root
        while path:
            val = path.popleft()
            if node.val * 2 + 1 == val and node.left:
                node = node.left
            elif node.val * 2 + 2 == val and node.right:
                node = node.right
            else:
                return False
        return True

1905. 统计子岛屿

1905. 统计子岛屿

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m = len(grid1)
        n = len(grid1[0])
        not_check_island = set()
        for i in range(m):
            for j in range(n):
                if grid1[i][j] == 0 and grid2[i][j] == 1:
                    not_check_island.add((i, j))

        island = []
        for i in range(len(grid2)):
            for j in range(len(grid2[i])):
                if grid2[i][j] == 1:
                    island_area = set()
                    ret = self.dfs(grid2, i, j, island_area, not_check_island)
                    if ret:
                        island.append(island_area)
        return len(island)

    def dfs(self, grid, i, j, island_area: set, not_check_island: set):
        if (i, j) in not_check_island:
            return False
        if grid[i][j] != 1:
            return True
        island_area.add((i, j))
        grid[i][j] = 2
        ret = []
        for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            if i + x < 0 or i + x >= len(grid) or j + y < 0 or j + y >= len(grid[x]):
                continue
            ret.append(self.dfs(grid, i + x, j + y, island_area, not_check_island))
        return all(ret)

1268. 搜索推荐系统

1268. 搜索推荐系统

字典树 + 二分法

import bisect

class Node:
    __slots__ = ['char', 'child', 'end_mark', 'child_vals']

    def __init__(self, char):
        self.char = char
        self.child_vals = []
        self.child = {}
        self.end_mark = False


class DictionaryTree:
    def __init__(self):
        self.root = Node(None)

    def add_word(self, word):
        node = self.root
        for c in word:
            if c in node.child:
                node = node.child.get(c)
            else:
                new = Node(c)
                node.child[c] = new
                bisect.insort(node.child_vals, c)
                node = new
        node.end_mark = True

    def dfs(self, node: Optional[Node], words: list, chars: list, limit: int):
        if node is None:
            return
        if len(words) >= limit:
            return
        if not node.child:
            words.append(''.join(chars))
            return
        if node.end_mark:
            words.append(''.join(chars))
        for k in node.child_vals:
            chars.append(k)
            self.dfs(node.child[k], words, chars, limit)
            chars.pop()


class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        dt = DictionaryTree()
        for word in products:
            dt.add_word(word)
        ans = []
        node = dt.root
        for i, c in enumerate(searchWord, start=1):
            if node:
                node = node.child.get(c)
            candidate_words = []
            dt.dfs(node, candidate_words, [searchWord[:i]], 3)
            ans.append(candidate_words)
        return ans

743. 网络延迟时间

743. 网络延迟时间

优先队列或使用最短路算法

import heapq
from collections import defaultdict


class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        net: Dict[int, list] = defaultdict(list)
        nodes = {i + 1 for i in range(n)}
        for u, v, w in times:
            net[u].append((v, w))
        priority_queue = [(0, k)]
        t = 0
        while priority_queue and nodes:
            t, node = heapq.heappop(priority_queue)
            nodes.discard(node)
            for v, w in net[node]:
                if v in nodes:
                    heapq.heappush(priority_queue, (t + w, v))
        if nodes:
            return -1
        return t