23.02.05 Today’s Leetcode

438. Find All Anagrams in a String (medium)

어제 풀었던 문제랑 매우 매우 유사해요.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n1, n2 = len(s), len(p)
        if n1 < n2:
            return []
        target = collections.Counter(p)
        counter = collections.Counter(s[:n2])
        res = []
        for i in range(n1 - n2):
            if counter == target:
                res.append(i)
            a, b = s[i], s[i + n2]
            counter[a] -= 1
            counter[b] += 1
        if counter == target:
            res.append(n1 - n2)
        return res

59. Spiral Matrix II (medium)

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        arr = [[0 for x in range(n)] for y in range(n)]

        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        p = 0
        cur = [0, 0]
        for i in range(n ** 2):
            next_ = [cur[0] + dirs[p][0], cur[1] + dirs[p][1]]
            if next_[0] < 0 or next_[0] >= n or next_[1] < 0 or next_[1] >= n:
                p = (p + 1) % 4
                next_ = [cur[0] + dirs[p][0], cur[1] + dirs[p][1]]
            elif arr[next_[0]][next_[1]] != 0:
                p = (p + 1) % 4
                next_ = [cur[0] + dirs[p][0], cur[1] + dirs[p][1]]

            arr[cur[0]][cur[1]] = i + 1
            cur = next_
        return arr 

60. Permutation Sequence (hard)

itertool을 이용한 꼼수 풀이.

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        temp = list(itertools.permutations([str(x) for x in range(1, n + 1)]))
        return ''.join(temp[k - 1])

다른 풀이

class Solution:
    def getPermutation(self, n: int, k: int) -> str:

        def getList(n, k):
            if k == 0:
                return [i for i in range(1, n+1)]
            
            block = math.factorial(n - 1)
            if k == block * n - 1:
                return [i for i in range(n, 0, -1)]

            first = k // block + 1
            k %= block
            
            res = getList(n-1, k)
            return [first] + [i if i < first else i + 1 for i in res]

        res = getList(n, k-1)
        return ''.join(map(str, res))