Category Archives: Recursive

Regular Expression Matching

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). The function prototype should be: bool isMatch(const char *s, … Continue reading

Posted in Recursive, String | Leave a comment

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: “((()))”, “(()())”, “(())()”, “()(())”, “()()()” C++: 01 void generateParenthesisHelp(vector<vector<string>>& A, 02                    … Continue reading

Posted in Array and linked list, Dynamic programming, Recursive | Leave a comment

Letter Combinations of a Phone Number

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”, … Continue reading

Posted in Array and linked list, Recursive, String | Leave a comment

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, … 1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2, then one 1” or 1211. Given an integer n, generate the nth sequence. Note: … Continue reading

Posted in Recursive, String | Leave a comment

Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements … Continue reading

Posted in Array and linked list, Recursive | Leave a comment

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. … Continue reading

Posted in Array and linked list, Recursive | Leave a comment

Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. C++: 01 void swap(vector<int>&num,int i, int j) 02 { 03     int t=num[i]; 04     num[i]=num[j]; 05     num[j]=t; … Continue reading

Posted in Array and linked list, Recursive | Leave a comment