Generalized Abbreviation

Write a function to generate the generalized abbreviations of a word. Note The order of the output does not matter. Example Input: "word" Output: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"] Example class Solution: def generateAbbreviations(self, word: str) -> List[str]: results = [] self.backtrack(results, word, "", 0, 0) return results def backtrack(self, results, word, curr, start, count): print(curr, start, count) # "" 0 0 # "" 1 1 # "" 2 2 # "" 3 3 # "" 4 4 # ------------ # 3d 4 0 # ------------ # 2r 3 0 # 2r 4 1 # ------------ # 2rd 4 0 # ------------ # 1o 2 0 # 1o 3 1 # 1o 4 2 # ------------ # 1o1d 4 0 # ------------ # 1or 3 0 # 1or 4 1 # ------------ # 1ord 4 0 # ------------ # w 1 0 # w 2 1 # w 3 2 # w 4 3 # ------------ # w2d 4 0 # ------------ # w1r 3 0 # w1r 4 1 # ------------ # w1rd 4 0 # ------------ # wo 2 0 # wo 3 1 # wo 4 2 # ------------ # wo1d 4 0 # ------------ # wor 3 0 # wor 4 1 # ------------ # word 4 0 # ------------ if start == len(word): if count > 0: curr += str(count) # curr could be "4" or "abcd" results.

by lek tin in "algorithm" access_time 2-min read

Word Ladder II

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Example 1 Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] Example 2 Input: beginWord = "hit" endWord = "cog" wordList = ["hot","dot","dog","lot","log"] Output: [] Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

by lek tin in "algorithm" access_time 2-min read

Palindrome Partitioning

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"] ] Solution # Time: O(n*2^n) # Space: `O(n)`. At any time, only one call stack will be in progress # For example, in put 'ababaaeqwds', one possible call stack will look like 'aba'->'b'->'aa'->'e'->'q'->'w'->'d'->'s': n space class Solution: def partition(self, s: str) -> List[List[str]]: if len(s) == 0 or s == None: return [] results = [] temp = [] self.

by lek tin in "algorithm" access_time 1-min read

Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. Each number in candidates may only be used once in the combination. Note All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. Example 1 Input: candidates = [10,1,2,7,6,1,5], target = 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] ###Example 2:

by lek tin in "algorithm" access_time 2-min read

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] Solution class Solution: def generateParenthesis(self, n: int) -> List[str]: """ :type n: int :rtype: List[str] """ ans = [] self.dfs(ans, '', 0, 0, n) return ans def dfs(self, ans, S, left, right, n): if len(S) == 2 * n: ans.

by lek tin in "algorithm" access_time 1-min read

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set). Note The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] Solution Time: O(n * 2^n) Space: O(n * 2^n) keep all the subsets of length N, since each of N elements could be present or absent. class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: results = [] subset = [] # Edge case 1 if nums == None: return results # Edge case 2 if len(nums) == 0: results.

by lek tin in "algorithm" access_time 1-min read

Subsets

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], [] ] Solution Time: O(n * 2^n) Space: O(n * 2^n) keep all the subsets of length N, since each of N elements could be present or absent. class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: results = [] subset = [] # Edge case 1 if nums == None: return results # Edge case 2 if len(nums) == 0: results.

by lek tin in "algorithm" access_time 2-min read

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. Note: All numbers will be positive integers. The solution set must not contain duplicate combinations. 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]] Solution class Solution: def combinationSum3(self, k: int, n: int) -> List[List[int]]: # Equivalent to subsets results = [] combination = [] # Start DFS self.

by lek tin in "algorithm" access_time 1-min read

Combination Sum

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 1 Input: candidates = [2,3,6,7], target = 7, A solution set is: [ [7], [2,2,3] ] Example 2 Input: candidates = [2,3,5], target = 8, A solution set is: [ [2,2,2,2], [2,3,3], [3,5] ] Solution class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: # Equivalent to subsets results = [] combination = [] # Edge cases if candidates == None: return results if len(candidates) == 0: results.

by lek tin in "algorithm" access_time 2-min read