Skip to main content

周赛 Weekly Contest 405

https://leetcode.cn/contest/weekly-contest-405

100339. Find the Encrypted String​

class Solution:
    def getEncryptedString(self, s: str, k: int) -> str:
        res = ""
        for i in range(len(s)):
            idx = (i+k) % len(s)
            res += s[idx]
        return res

100328. Generate Binary Strings Without Adjacent Zeros​

class Solution:
    def validStrings(self, n: int) -> List[str]:
        res = []
        def dfs(i, isLastZero, tmpList):
            if i == n:
                nonlocal res
                res.append("".join(tmpList))
                return

            tmpList.append("1")
            dfs(i+1, False, tmpList)
            tmpList.pop(-1)
            if not isLastZero:
                tmpList.append("0")
                dfs(i+1, True, tmpList)
                tmpList.pop(-1)
        dfs(0, False, [])
        return res

100359. Count Submatrices With Equal Frequency of X and Y​

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        def sumF(f1, f2):
            s = [0, 0, 0]
            for i in range(3):
                s[i] += f1[i] + f2[i]
            return s

        ans = 0
        f = [[0, 0, 0] for _ in range(len(grid[0]))]
        for i in range(len(grid)):
            tmpF = [0, 0, 0]
            for j in range(len(grid[0])):
                if grid[i][j] == "X":
                    tmpF[0] += 1
                elif grid[i][j] == "Y":
                    tmpF[1] += 1
                else:
                    tmpF[2] += 1

                s = sumF(f[j], tmpF)
                if s[0] == s[1] and s[0] > 0:
                    ans += 1
                f[j] = s
        return ans

100350. Construct String with Minimum Cost​

TLE

class Solution:
    def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:
        # O(n^2)
        # 状压 dp
        minCost = -1

        w2Idx = dict()
        for i in range(len(words)):
            word = words[i]
            if word not in w2Idx:
                w2Idx[word] = costs[i]
            elif costs[i] < w2Idx[word]:
                w2Idx[word] = costs[i]
        # print(w2Idx)
        
        @cache
        def dp(i, sumCost):
            if i == len(target):
                nonlocal minCost
                if minCost == -1:
                    minCost = sumCost
                else:
                    minCost = min(minCost, sumCost)
                return
            
            tmp = ""
            for j in range(i, len(target), 1):
                tmp += target[j]
                if tmp in w2Idx:
                    dp(j+1, sumCost+w2Idx[tmp])
        dp(0, 0)
        return minCost