Tag Archives: recursion

Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it. Each element is either an integer, or a list — whose elements may also be integers or other lists. Example 1: Given the list [[1,1],2,[1,1]], By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].… Read More »

Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, – and *. Example 1 Input: “2-1-1”. ((2-1)-1) = 0 (2-(1-1)) = 2 Output: [0, 2] Example 2 Input: “2*3-4*5” (2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5)… Read More »

Strobogrammatic Number II, III

Strobogrammatic Number II A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. For example, Given n = 2, return [“11″,”69″,”88″,”96”]. Solution. The basic idea is to iterate from inside to outside. If n is even, we… Read More »

Generate all combination of parenthesis

Given a number of pair parenthesis. Generate all combinations. For example n = 2, then should return ArrayList<String> = [“(())”, “()()”]; The solution is like below. public static ArrayList<String> generateParenthesis(int n) { // Write your code here ArrayList<String> list = new ArrayList<String>(); parenthesisHelper(0, 0, n, list, “”); return list; } public static void parenthesisHelper(int open,… Read More »

possible sum of a number

Given a number n, find all sub sets: For example given 4, should return [[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]] My Solution: public static List<List<Integer>> permutateNumber(int n) { List<List<Integer>> result = new ArrayList<List<Integer>>(); List<Integer> currResult = new ArrayList<Integer>(); permutateNumberUtil(result, currResult, n, 1); return result; } public static void permutateNumberUtil(List<List<Integer>> result,… Read More »

Wild card match

This post responds to junmin’s code: link Below is my recursion implementation for ‘?’ and ‘*’ regular expression match: public static boolean matchReg(String str, String reg) { return matchRegUtil(str, 0, reg, 0); } public static boolean matchRegUtil(String str, int strPos, String reg, int regPos) { if(strPos>=str.length() && regPos>=reg.length()) { return true; } else if(regPos>=reg.length()) {… Read More »

Permutation, Subset, All group of Palindrome

Today, I found a great coding style for series problem, like permutation, subset and group of palindrome: public static void getPermutationUtil(String str, int start, List<List<String>> result, List<String> currResult) { if(start==str.length()) { ArrayList<String> curr = new ArrayList<String>(currResult); result.add(curr); } else { for(int i=start; i<str.length(); i++) { String currStr = str.substring(start, i+1); currResult.add(currStr); getPermutationUtil(str, i + 1, result,… Read More »

super set by bit array

This is my try for super set problem given by junmin link. Given a set of unique characters, generate its superset. example: a, b, c, its superset are: [[], [c], [b], [c, b], [a], [c, a], [b, a], [c, b, a]] Normal way is to use recursion. But another way is to use bit array.… Read More »

Water jug problem

And I found this water jug problem when I’m reading Number Theory. It is interesting. Let me start by defining the problem: Assume we have 2 jugs. Jug1 can contains 3 galons water, jug2 can contains 5 galons water. We can pour water into jug1 and jug2, empty 2 jugs, or we can pour water between 2… Read More »