leetcode 110(이진 트리), 1079(백트래킹, subset), 1286(백트래킹), 1641(dp)

110 leetcode.com/problems/balanced-binary-tree/
문제를 이해하는데 시간이 좀 걸렸다. 모든 노드에서 각각의 서브트리의 높이 차가 1 초과로 나면 안된다. 1까지의 높이차이는 balanced되었다고 판별한다. 각각의 서브트리를 판별해야 하므로 재귀적으로 풀어야 한다.

class Solution(object):
    def isBalanced(self, root):
        if not root:
            return True
        
        def check(root):
            if not root:
                return 0
            l = check(root.left)
            r = check(root.right)
            if l == -1 or r == -1 or abs(l - r) > 1:  # 좌,우 자식의 높이차가 1 초과로 나면 -1을 돌려주는데, 이미 서브트리중 하나에서 -1이 나왔으면 그냥 바로 안되는거로 판별하고 -1을 리턴한다.
                return -1
            return max(l, r) + 1
        return check(root) != -1

1079 leetcode.com/problems/letter-tile-possibilities/
모든 타일의 경우의 수를 구해야 한다. 단순히 부분집합이 아니라 예시에서 AB, BA가 다른 경우로 보이는거로 보아, 타일의 길이 제한조건이 7로 짧다는 점에서도 시간복잡도는 고려하지 않아도 되고 모든 경우에 대해서 가져오도록 짜면 될것같다.

class Solution(object):
    def numTilePossibilities(self, nums):
        ret = []
        def dfs(cur, nums):
            for i in xrange(len(nums)):
                ret.append(cur + nums[i])  # 모든 경우의 수를 저장해놓는다.
                dfs(cur + nums[i], nums[:i] + nums[i+1:])  # 현재 사용한것만 빼고 다시 모든 경우의 수를 돌린다.
        dfs('', nums)
        return len(set(ret))  # 중복제거

1286 leetcode.com/problems/iterator-for-combination/
모든 조합 경우의 수를 구하는 문제이다. 파이썬에는 모듈 갖다 쓰면 되는데 실제 면접에서는 안될것이므로 구현한다. 제한조건의 길이가 1~15이므로 시간복잡도는 고려하지 않아도 될것같고 구현에 중점을 둔다.

class CombinationIterator(object):
    def __init__(self, c, l):
        self.comb_list = []
        def backtrack(comb, index):
            if len(comb) == l:
                self.comb_list.append(comb)
                return
            for i in xrange(index+1, len(c)):
                backtrack(comb+c[i], i)
        for i in xrange(len(c)):
            backtrack(c[i], i)
            
    def next(self):
        return self.comb_list.pop(0)

    def hasNext(self):
        return bool(self.comb_list)

1641 leetcode.com/problems/count-sorted-vowel-strings/

# n=1 5
# n=2 5 + 4 + 3 + 2 + 1 = 15
# n=3 (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + 1 = 35
# n=4 = (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + 1 +
# (4+3+2+1) + (3+2+1) + (2+1) + 1 +
# (3+2+1) + (2+1) + 1 +
# (2+1) + 1 +
# 1 = 70

n=2까지는 기본값으로 초기화해주고 n값이 3일때부터 이전정보를 참고한다. 위를 참고하여 짜준다.

class Solution(object):
    def countVowelStrings(self, n):
        # n=1 5
        # n=2 5 + 4 + 3 + 2 + 1 = 15
        # n=3 (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + 1 = 35
        # n=4 = (5+4+3+2+1) + (4+3+2+1) + (3+2+1) + (2+1) + 1 + 
        #       (4+3+2+1) + (3+2+1) + (2+1) + 1 +
        #       (3+2+1) + (2+1) + 1 +
        #       (2+1) + 1 +
        #       1 = 70
        #n = 3
        dp = [[0]*5 for i in range(50)]  # n의 제한조건이 50이며, 각각 aeiou로 만들수있는 갯수를 나타낸다.
        dp[0][0] = 5  # n=1일경우 초기화
        dp[1] = [5,4,3,2,1]  # n=2일경우 초기화
        for i in range(2, n):  # n=3부터 이전 정보를 참고한다.
            for j in range(5):
                dp[i][j] = sum(dp[i-1][j:])
        return sum(dp[n-1])