backtracking
-
[LeetCode] Combination Sum알고리즘 2020. 5. 4. 16:39
문제 Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example..
-
[LeetCode] Word Break II알고리즘 2019. 12. 19. 17:07
문제 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Note: The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words. Example 1: Input: s = "catsanddo..
-
[LeetCode] Palindrome Partitioning알고리즘 2019. 12. 7. 15:57
문제 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"], ["a","a","b"] ] Approach DFS로 string을 i글자씩 잘라가며 palindrome인지 확인한 후 palindrome이면 자르고 남은 string을 재귀함수를 통해 다시 잘라 확인하여 최종적으로 자른게 모두 palindrome이면 답 배열에 추가한다. Code https://github.com/chi3236/algorithm/blob/master/Leet..
-
[LeetCode] Word Search알고리즘 2019. 11. 19. 17:52
문제 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE"..
-
[LeetCode] Subsets알고리즘 2019. 11. 18. 17:30
문제 Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Approach 전형적인 Bactracking문제로 n개의 요소로 된 집합에서 0개짜리 부분집합 ~ n개짜리 부분집합을 DFS등을 써서 backtracking으로 찾아가면 된다. Discussion을 보니까 bit manipulation으로 푸는 방법도 있던데 이건 좀 신박 Code h..
-
[LeetCode] Regular Expression Matching알고리즘 2019. 9. 21. 01:24
문제 Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Note: s could be empty and contains only lowercase letters a-z. p could be empty and contains only lowercase letters a-z, and charact..