[leetcode]140. Word Break II, 파이썬
문제 릿코드 문제 링크 풀이 난이도 : hard 풀이, dfs 주어진 wordDict을 돌며 해당 단어로 시작하면 재귀로 돌려줌 s가 빈 채로 인자로 넘어왔다는 뜻은 주어진 wordDict 배열 원소로 문장 s가 완성 가능하다는 뜻이므로 ret에 words 리스트를 더해줌 문제 조건에 맞춰 리턴 코드 class Solution: def wordBreak(self, s, wordDict): ret = [] self.dfs(s, wordDict, ret, []) for i, e in enumerate(ret) : ret[i] = ' '.join(e) return ret def dfs(self, s, wordDict, ret, words): if not s: ret.append(words) fo..
40. Combination Sum II, 파이썬
예전에 풀었을 때는 시간초과 때문에 틀렸던 것 같다. [1, 1, 1, 1, 1, 1, 1] 등에서 시간초과가 났었다 문제 1. 숫자들이 배열로 주어졌을 때 합이 target인 숫자 조합을 중복 없이 구하는 것. 풀이 1. 어려운 문제는 아니지만 중복을 피하고, 시간을 줄이는 것이 핵심. 2. target 8, [1, 1, 4, 6, 7] 이라고 했을 때 [1, 1, 6] 은 체크하고 [1, 7], [1, 7] 이 중복이 나오지 않게 해야한다. 3. 따라서 정렬된 배열에서 path에서 arr[i] 값이 중복되어 다음 dfs로 넘어가지 않도록 체크해준다. class Solution(object): def combinationSum2(self, candidates, target): ret = [] self...