Posts

Showing posts with the label Backtracking

[LeetCode] 425. Word Squares

Given a set of words  (without duplicates) , find all  word squares  you can build from them. A sequence of words forms a valid word square if the  k th  row and column read the exact same string, where 0 ≤  k  < max(numRows, numColumns). For example, the word sequence  ["ball","area","lead","lady"]  forms a word square because each word reads the same both horizontally and vertically. b a l l a r e a l e a d l a d y Note: There are at least 1 and at most 1000 words. All words will have the exact same length. Word length is at least 1 and at most 5. Each word contains only lowercase English alphabet  a-z . Example 1: Input: ["area","lead","wall","lady","ball"] Output: [ [ "wall", "area", "lead", "lady" ], [ "ball", "area", "lead", "lady" ] ] Explanation: The ou...

[LeetCode] 216. Combination Sum III

Find all possible combinations of  k  numbers that add up to a number  n , given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input:  k  = 3,  n  = 7 Output: [[1,2,4]] Example 2: Input:  k  = 3,  n  = 9 Output: [[1,2,6], [1,3,5], [2,3,4]] Thought process: DFS + backtracking. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public List < List < Integer >> combinationSum3 ( int k , int n ) { List < List < Integer >> combinations = new ArrayList <>(); combinationSum3 ( k , n , 1 , new ArrayList <>(), combinations ); return combinations ; } private void combinationSum3 ( int k , int n , int start , List < Integer > combination , List < List < Integer >> combinati...

[LeetCode] 211. Add and Search Word - Data Structure Design

Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters  a-z  or  . . A  .  means it can represent any one letter. For example: addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note: You may assume that all words are consist of lowercase letters  a-z . click to show hint. You should be familiar with how a Trie works. If not, please work on this problem:  Implement Trie (Prefix Tree)  first. Thought process: Use trie. addWord: iterate through the word. Start from the root trie node. If current character does not map to a trie node, create a new one and map them. Otherwise, go to the next trie node. Search: iterate through the word. If current character is ...

[LeetCode] 44. Wildcard Matching

Implement wildcard pattern matching with support for  '?'  and  '*' . '?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") ? false isMatch("aa","aa") ? true isMatch("aaa","aa") ? false isMatch("aa", "*") ? true isMatch("aa", "a*") ? true isMatch("ab", "?*") ? true isMatch("aab", "c*a*b") ? false Thought process: Recursively match s and p's substrings. Base case: If s and p are both empty, return true. If p's length is 1: If p is *, return true. If p is ? and s's length is 1, return true. Else if s and p are equal, return true. Recurrence: If p's first char...

[LeetCode] 17. Letter Combinations of a Phone Number

Image
Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Input: Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. Thought process: Store number => character mappings in a map. Iterate through the phone number and get every possible combination. Recursively add and delete character from a string builder. The base case is when the StringBuilder.length() == digits.length(). Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { private String [] map = { " " , "" , "abc" , "def" , "ghi" , "...

[LeetCode] 90. Subsets II

Given a collection of integers that might contain duplicates,  nums , return all possible subsets. Note:  The solution set must not contain duplicate subsets. For example, If  nums  =  [1,2,2] , a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Thought process: Based on the solution to "78. Subsets" , sort the array before recursion. For each iteration, if current index is larger than the starting index of this recurrence, and current number equals its previous number, that means it'll create a duplicate subset if it's added to the current subset, because that subset has already been accounted for by the previous number. So continue. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class Solution { public List < List < Integer >> subsetsWithDup ( int [] nums ) { List < List < Integer >> subsets = new ArrayList <>(); List < Integer ...

[LeetCode] 78. Subsets

Given a set of  distinct  integers,  nums , return all possible subsets. Note:  The solution set must not contain duplicate subsets. For example, If  nums  =  [1,2,3] , a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Thought process: Iterate through the list. For each number, iterate through the list again starting from that element. As I iterate, add elements to the current list. Delete the last added element after the recurrence. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Solution { public List < List < Integer >> subsets ( int [] nums ) { List < List < Integer >> subsets = new ArrayList <>(); List < Integer > subset = new ArrayList <>(); subsets ( nums , 0 , subset , subsets ); return subsets ; } private void subsets ( int [] nums , int start , ...