leetcode 139(bfs, worddict), 42(trapping rain water), 692(구현)

139 https://leetcode.com/problems/word-break/

bfs로 풀었다.

from collections import deque
class Solution(object):
    def wordBreak(self, s, wordDict):
        #s = "catsanddog"
        #wordDict = ["cats", "dog", "sand", "and", "cat"]
        
        visited = set()
        wordDict = set(wordDict)
        queue = deque()
        for i in xrange(len(s)+1):
            if s[:i] in wordDict:
                visited.add(s[i:])
                queue.append(s[i:])
                
        #print 'queue =',queue
        
        while queue:
            p = queue.popleft()
            if p == '':
                return True
            for i in xrange(len(p)+1):
                if p[:i] in wordDict and p[i:] not in visited:
                    visited.add(p[i:])
                    queue.append(p[i:])
        return False

42 https://leetcode.com/problems/trapping-rain-water/

가장 높은곳의 인덱스를 찾은 후에 가장 높은 높이까지 반복한다.

왼쪽에서 오른쪽으로 가면서 (왼쪽 최대 높이 - 현재 높이)만큼 물의 갯수를 더해주면서 왼쪽 최대 높이를 갱신해준다. 단순하게 (왼쪽 최대 높이 - 현재 높이)만큼 물의 갯수를 더해주면 되는 이유는 왼쪽이 아무리 높아도 중간 어딘가에 있는 최대 높이까지만 반복하기 때문에 그 차액만큼이 물의 높이이기 때문이다.

오른쪽도 마찬가지로 오른쪽부터 왼쪽으로 가면서 동일하게 반복해준다.

class Solution(object):
    def trap(self, height):
        if len(height) < 2:
            return 0
        
        max_index = height.index(max(height)) 
        water = 0
        
        left_max = height[0]
        for i in xrange(1, max_index):
            left_max = max(left_max, height[i])
            water += left_max - height[i]
        
        right_max = height[len(height)-1]
        for i in xrange(len(height)-2, max_index, -1):
            right_max = max(right_max, height[i])
            water += right_max - height[i]
        return water

692 https://leetcode.com/problems/top-k-frequent-words/

그냥 시키는대로 구현해준다.

class Solution(object):
    def topKFrequent(self, words, k):
        f = {}
        for word in words:
            f[word] = f.get(word, 0) + 1
        return map(lambda x: x[0], sorted(f.iteritems(), key=lambda x:(-x[1], x[0]))[:k])