Leetcode 890, 797(dfs), 856(스택)

https://leetcode.com/problems/find-and-replace-pattern/

이 문제는 사실 별거없다. 단어들을 패턴화시킨후 그 패턴에 맞는 단어를 찾는 문제이다. 난 별생각없이 패턴화시키는 로직이 딱히 안떠올라서 'cee'같은 문자의 경우 첫번째 나오는 c는 a로, 두번째 나오는 단어 e는 b로.. 이런식으로 패턴화를 했다. 코드를 짜긴 했지만 별로 만족스럽진 못했다. 별로 좋은 답은 아니니 일단 접어둠.

class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        """
        :type words: List[str]
        :type pattern: str
        :rtype: List[str]
        """
        pattern_dict = {}
        _word_pattern = ''
        d = 97
        for w in pattern:
            if w not in pattern_dict:
                pattern_dict[w] = chr(d)
                _word_pattern += chr(d)
                d += 1
            else:
                _word_pattern += pattern_dict[w]
        
        ret = []
        for word in words:
            pattern_dict = {}
            word_pattern = ''
            d = 97
            for w in word:
                if w not in pattern_dict:
                    pattern_dict[w] = chr(d)
                    word_pattern += chr(d)
                    d += 1
                else:
                    word_pattern += pattern_dict[w]
            if word_pattern == _word_pattern:
                ret.append(word)
        return ret

근데 discuss에 내가 힘겹게 짠 코드를 단 5줄로 줄여버리는 분이 등장한다..(결론적으로 동일한 로직이라서 줄여버렸다고 표현함.)

https://leetcode.com/problems/find-and-replace-pattern/discuss/161288/C%2B%2BJavaPython-Normalise-Word

def findAndReplacePattern(self, words, p):
        def F(w):
            m = {}
            return [m.setdefault(c, len(m)) for c in w]
        return [w for w in words if F(w) == F(p)]

패턴화라는 말을 normalise라고 표현했는데(이게 공식 표기가 맞는듯) 단순히 dictionary의 길이를 이용해서 해버렸다. 난 아직 많이 멀었다...

https://leetcode.com/problems/all-paths-from-source-to-target/

뭔가 복잡한 그래프 문제처럼 보이지만 간단한 dfs이다.

class Solution(object):
    def allPathsSourceTarget(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[List[int]]
        """
        if graph[0] == []:
            return []
        
        N = len(graph)
        path = {}
        for i, g in enumerate(graph):
            path[i] = g
        
        stack = [[path[0], [0]]]
        ret_path = []
        while stack:
            # print 'stack =',stack
            p, path_history = stack.pop()
            for each_path in p:
                if each_path == N-1:
                    ret_path.append(path_history + [each_path])
                    continue
                if each_path not in path_history:
                    path_history.append(each_path)
                    for next_path in path[each_path]:
                        if next_path not in path_history:
                            stack.append([[next_path], path_history[:]])
                    path_history.pop()
        return ret_path

https://leetcode.com/problems/score-of-parentheses/

당연히 스택을 이용해서 풀었는데 이것보다 쉬운 해답이 존재한다.

class Solution(object):
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        stack = []
        for s in S:
            if s == ')':
                p = stack.pop()
                if type(p) is int:
                    while True:
                        pp = stack.pop()
                        if type(pp) is int:
                            p += pp
                        else:
                            break
                    stack.append(p * 2)
                else:
                    stack.append(1)
                    continue
            else:
                stack.append(s)
        return sum(stack)

https://leetcode.com/problems/score-of-parentheses/discuss/141778/1-line-Python 를 보면

def scoreOfParentheses(self, S):
        return eval(S.replace(')(', ')+(').replace('()', '1').replace(')', ')*2'))

이렇게 아주 간단하게 풀어놨다.(맨 위에 간단하게 짠 그분과 동일한분) 똑똑하다.