Int to Roma

public String intToRoman(int num) {
String digit[] = new String[]{“”, “I”,”II”,”III”,”IV”, “V”,”VI”,”VII
“,”VIII”,”IX”};
String ten[] = new String[]{“”, “X”,”XX”,”XXX”,”XL”,”L”,”LX”,”LXX”,
“LXXX”,”XC”};
String hundred[] = new String[]{“”, “C”, “CC”, “CCC”, “CD”, “D”, “DC
“, “DCC”, “DCCC”, “CM”};
String thousand []= new String[] {“”, “M”, “MM”, “MMM”};
StringBuffer result = new StringBuffer();
if(num >3999)
num = 3999;
if(num<0)
num = 0;
result.append(thousand[num/1000]);
result.append(hundred[num/100 %10]);
result.append(ten[num/10 %10]);
result.append(digit[num%10]);
return result.toString();

}

Distinct subsets for an array with duplicated elements

Question: In an array with duplicated elements, how to find its distinct subsets?

Example, when arr = {1,2,3,4} we have 16 distinct subsets as {}, {1}, {1,2},{1,2,3},{1,2,3,4},{1,2,4},{1,3},{1,3,4},{1,4},{2},{2,3},{2,3,4},{2,4},{3},{3,4},{4},

However, when arr = {1,2,2,4} we only have 12 distinct subsets as {}, {1}, {1,2},{1,4},{1,2,2},{1,2,2,4},{1,2,4},{2},{2,2},{2,2,4},{2,4},{4},

Solution:

1) The most intuitive way is to find out all possible subsets and put them into hashtable, and then display only keys. It is easy to implement, however, takes lot of additional memory, assume that when we have an array with 10000 elements while all elememnt is “1”, in this way one needs to have 2^1000 space to store all possible subsets, however, we both know that there are only 1001 distinct subsets as {}, {1},{1,1},…,{1,1….1}.

2) To solve this issue, we need a better approach. This blog suggests an efficient approach that decompose the problem into either generate the subsets from all distinct elements, or generate subsets from all duplicate elements.

The algorithm goes as following:
1) For a given array Arr, find out its elements which only appear once, put them into Arr_distinct. For elements which appear multiple times, put them into hashtable where the key is this element, and the value is the times it appears.

2) Find out all subsets from Arr_distinct, denoted as SubSets

3) For the elements which appear multiple times, create their subsets SubSets_for_num. For example, if “2” appear 3 time, SubSets_for_2 ={2}, {2,2} and {2,2,2}

4) For each element subset in the SubSets, create new datasets which is combined by subset and all the SubSets_for_num created in step 3) and one element at a time. That is, supposse in step 3) we have numbers “2” and “3”, both appear 3 times, then in this iteration all ELEs are only concatenated with SubSets_for_2, the SubSets_for_3 will be added in next iteration. After that, the new geneated dataset are included into SubSets to make it larger.

5) Repeat step 4) untill all the duplicated numbers are merged.

Examples: Arr = {1,2,2,3,3,4,5}
Arr_distinct = {1,4,5}, we have two groups of subsets for duplicated elements, those are: {2},{2,2} and {3}, {3,3}

First of all, we find out all possible subsets (including empty subset) from Arr_distinct. It has 8 subsets as Subset = {{},{1},{1,4},{1,4,5},{1,5},{4},{4,5},{5}}.

public static List<List> CombinationWithUniqueArray(int[] arr,
        int index, List list, List<List> solution)
{
     solution.Add(list.ToList());
     for (int i = index; i < arr.Length; i++)
     {
         list.Add(arr[i]);
         CombinationWithUniqueArray(arr, i + 1, list, solution);
         list.RemoveAt(list.Count - 1);
     }
     return solution;
}

Next, add {2} and {2,2} to all the elements in Subset, now we have the following 16 new subset
newCreatedSubset = {
{2},{1,2},{1,4,2},{1,4,5,2},{1,5,2},{4,2},{4,5,2},{5,2} //add {2}

{2,2},{1,2,2},{1,4,2,2},{1,4,5,2,2},{1,5,2,2},{4,2,2},{4,5,2,2},{5,2,2}  // add {2,2}}

After we put the newCreatedSubset back into Subset, the size of Subset becomes 24 as:
Subset = {{},{1},{1,4},{1,4,5},{1,5},{4},{4,5},{5},
{2},{1,2},{1,4,2},{1,4,5,2},{1,5,2},{4,2},{4,5,2},{5,2},
{2,2},{1,2,2},{1,4,2,2},{1,4,5,2,2},{1,5,2,2},{4,2,2},{4,5,2,2},{5,2,2}}

Now, we add {3} and {3,3} to each element in Subset to get 48 new subsets:

newCreatedSubset = {{3},{1,3},{1,4,3},{1,4,5,3},{1,5,3},{4,3},{4,5,3},{5,3},
{2,3},{1,2,3},{1,4,2,3},{1,4,5,2,3},{1,5,2,3},{4,2,3},{4,5,2,3},{5,2,3},
{2,2,3},{1,2,2,3},{1,4,2,2,3},{1,4,5,2,2,3},{1,5,2,2,3},{4,2,2,3},{4,5,2,2,3},{5,2,2,3} // add{3}

{3,3},{1,3,3},{1,4,3,3},{1,4,5,3,3},{1,5,3,3},{4,3,3},{4,5,3,3},{5,3,3},
{2,3,3},{1,2,3,3},{1,4,2,3,3},{1,4,5,2,3,3},{1,5,2,3,3},{4,2,3,3},{4,5,2,3,3},{5,2,3,3},
{2,2,3,3},{1,2,2,3,3},{1,4,2,2,3,3},{1,4,5,2,2,3,3},{1,5,2,2,3,3},{4,2,2,3,3},{4,5,2,2,3,3},{5,2,2,3,3} //add {3,3}}

After we merge the Subset and the NewCreatedSubset, we have 72 distinct subset in total.

 public static List<List> DistinctCombination(int[] arr)
{
   var dict = new Dictionary<int, int>();
   ListuniqueList = new List();
   foreach(int num in arr)
   {
      if (dict.ContainsKey(num))
      dict[num]++;
      else  dict.Add(num, 1);
   }
   foreach(int num in arr)
   {
       if(dict[num]==1)
       uniqueList.Add(num);
    }
   var solution = CombinationWithUniqueArray(uniqueList.ToArray(), 0, new List(),
                newList<List>());
   foreach (int num in dict.Keys)
   {
       if (dict[num] == 1)
            continue;
       List<List> appendSolution = new List<List>(),
                       duplicateElement = new List<List>();
       List temp = new List();
       for (int i = 0; i < dict[num]; i++)
       {
           temp.Add(num);
           duplicateElement.Add(temp.ToList());
       }
       foreach (var iter in solution)
       {
           foreach (var dup in duplicateElement)
           {
              List newIter = iter.ToList();
              newIter.AddRange(dup);
              appendSolution.Add(newIter);
            }

        }
        solution.AddRange(appendSolution);
   }
   return solution;
}

Number of ways to construct desired BST

A BST can be constructed from a list of integers with different orders. For example, [4,2,1,3,7,5,8,10] and [4,7,5,8,10,2,3,1] may generate the same BST.

Question: Given a BST, find out the number of integer lists that can generate this BST.

Solution: Based on the following figure, let us do a pre-order traversal, and get a list of possible integers: {4,2,1,3,7,5,8,10}.

It could be noticed that the integers that are smaller than the first entry of the list are the left subTree of the BST. The integers that are greater than the first entry of the list are the right subTree of the BST. Therefore, the input list can be represent as {4, [2,1,3] [7,5,8,10]}.

Furthermore, according to the property of the BST, as long as the relative order of the integers are maintained, the same BST can be generated. For example, in this case {4, [2,[7,5,8,10],1,3]}, or {4, [2,[7,5],1,[8,10],3]}, can generate the same BST.

Therefore, this problem can be converted to the following

Q: How many different ways to maintain the relative orders of the integers in the given list?

To solve this question, we first need to specify tree entries from this list and which will be filled with (2, 1, 3) to form the left subTree. By doing that, the remained 4 entries (excluding the first entry, that is the root) will be filled with (7, 5, 8, 10) to form the right subTree. The questions now becomes: How many different ways can we select such 3 entries (left subTree)? The answer is obvious, it is easy to get that there are 7 choose 3 = 35 ways. Such question can be also represented as How many different ways can we select such 4 entries (right subTree)? The answer is obvious, it is easy to get that there are 7 choose 4 = 35 ways.

Next, the problem becomes how to fill such entry, we can use a recursive way to solve it. For the 3 entries, it should be filled with 2,1 and 3. The root should always be 2, and its left subTree should be (1) and its right subTree should be (3), Therefore, out of is 2 entries (excluding the root entry 2), we need to find out how many ways the left subTree (1) can be placed, the answer should be (2 choose 1) = 2.

For the 4 entries that should be filled with 7,5,8,10. The root is always be 7, and its left subTree should be (5) and its right subTree should be (8,10), therefore, out of its 3 entries, we need to find out how many ways to specify a entry that can be filled with (5) or (8,10). The answer is (3 choose 1) = 3.

I am tired to repeat the process of constructing the tree (8,10). In a similar manner, root is 8, and the answer is (1 choose 1) = (1 choose 0) = 1.

All in all, in this case there are (7 choose 3, root is 4) * (2 choose 1, root is 2) * (3 choose 1, root is 7) * (1 choose 1, root is 8) = 210 ways to construct the desired BST.

Algorithm:

For a given list of integers List.Recursively do the following:
1) If the size of the List is less than 1. return 1.
2) Considering the first entry of the list as the root of the current tree, the rest of the integers in the list should be compared to the root and be treated as the left-subtree, L1, and right-subtree, L2. Be awared that the order of the integers in L1 and L2 should be the same as they are in the list L. After that, Finding out the number of ways to place L1. that is, SizeOf(L)-1 choose SizeOf(L1), and can be denoted as N1.
3) Apply this approach to L1 and L2, the returned values can be denoted as SubN1 and SubN2, return N1 * SubN1 * SubN2.

public static int numberOfWaysToConstructBST(List<int> list)
{
    if (list.Count <= 1)
    return 1;
    else
    {
       List<int> smaller = new List<int>();
       List<int> greater = new List<int>();
       for (int i = 1; i < list.Count; i++)
         if (list[i] < list[0])
            smaller.Add(list[i]);
         else
            greater.Add(list[i]);
       return mChooseN(list.Count - 1, smaller.Count) *
              numberOfWaysToConstructBST(smaller) *
               numberOfWaysToConstructBST(greater);
    }
}

public static int mChooseN(int m, int n)
{
    if (m < 0 || n < 0 || n>) throw new Exception();
    n = m - n > n ? n : m - n;
    int top = 1, bottom = 1;
    while (n > 0)
    {
       top = top * m--;
       bottom = bottom * n--;
    }
     return top / bottom;
}

Project Euler, problem 82

Here is the link to the project euler questions: http://projecteuler.net/problem=82

It is not difficult to find out the answer: 260324. The challenge is, how to find out the minimum time complexity.

By means of minimum time, the recursive approach is not recommended. That is, if you start with finding out all the possible paths from leftmost column to the rightmost column, then you are in the wrong way. Actually you may get the correct answer but it will takes more than 1 minutes.

A better approach is to use DP approach, there is a very similar problem listed in http://www.leetcode.com/2010/11/unique-paths.html, however, in our problem we do not necessary to go from the left-top to the right-bottom. Furthermore, in LeetCode the route can only goes right and goes down, however, in this case we can go right, go down, and go up, which makes the following path possible.

Therefore, the purpose of the proposed approach is, for each entry in the 2-D array, we only cares the minimum path-weight up to this entry. Furthermore, since it can never go left, for an entry Arr[i][j], we only need to find out the minimum cost when one go from Arr[K][j-1] where K is 1 to 80 (0 to 79) in the problem. To be more specific, in the sample code we use Arr1 to represent the source 2-D array, the Arr2 is used to present the minimum cost spent to reach each entry. The Arr3 is another auxiliary array, it is used to find out the cost that go from Arr[K][j-1] to Arr[i][j]. You need to consider the following case:

The time complexity is O(n^3) for sure. In my machine, I get the result in less than a second.

Java Code:

public static int minimumPath() throws NumberFormatException, IOException
	{

		int[][] arr1 = new int[80][80], arr2 = new int[80][80], arr3 = new int[80][80];
		File file = new File("C:\\matrix.txt");
		StringBuffer contents = new StringBuffer();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new FileReader(file));
            String text = null;
            int rowIndex = 0;
            while ((text = reader.readLine()) != null) {
                String[] strArr = text.split(",");
                for(int i=0;i<strArr.length;i++)
                	arr1[rowIndex][i] = Integer.parseInt(strArr[i].trim());
                rowIndex++;
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
		for(int i=0;i<80;i++)
		{
			arr2[i][0] = arr1[i][0];
		}
		//from the second column to the second rightmost column
		for(int j=1;j<80-1;j++)
		{
		   for(int i=0;i<80;i++)
		   {
			   int min = Integer.MAX_VALUE;
			   // reach from its upper left path
			   for(int k=0;k<i;k++)
			   {
				   //start from arr2[k][j-1], going right and down
				   arr3[k][j-1] = arr2[k][j-1];
				   arr3[k][j]   = arr3[k][j-1]+arr1[k][j];
				   int l = k+1;
				   while(l<i)
				   {
                                arr3[l][j-1] = arr3[l-1][j-1] + arr1[l][j-1];
				          arr3[l][j]   = Math.min(arr3[l][j-1], arr3[l-1][j])+arr1[l][j];
                                          l++;
                                   }
                                   int temp = Math.min(arr3[i-1][j-1]+arr1[i][j-1], arr3[i-1][j]);
                                    min = Math.min(temp, min);
                           }

                           // reach from its bottom left path
                           for(int k=79;k>i;k--)
			   {
				   //start from arr2[k][j-1], going right and up
				   arr3[k][j-1] = arr2[k][j-1];
				   arr3[k][j]   = arr3[k][j-1]+arr1[k][j];
				   int l = k-1;
				   while(l>i)
				   {
					   arr3[l][j-1] = arr3[l+1][j-1] + arr1[l][j-1];
					   arr3[l][j]   = Math.min(arr3[l][j-1], arr3[l+1][j])+arr1[l][j];
					   l--;
				   }
				   int temp = Math.min(arr3[i+1][j-1]+arr1[i][j-1], arr3[i+1][j]);
				   min = Math.min(temp, min);
			   }

			   //reach from its left'
			   min = Math.min(arr2[i][j-1], min);
			   arr2[i][j] = arr1[i][j] + min;
		   }
		}
		//find min from rightmost column
		int min = Integer.MAX_VALUE;
		for(int i=0;i<80;i++)
		{
			min = Math.min(arr2[i][78]+arr1[i][79], min);
		}
		return min;
	}

Google scramble string (III)

Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg”
tiger
/    \
ti    ger
/  \   /   \
t    i  g    er
/  \
e    r

itreg
/    \
it     reg
/  \   /   \
t    i  g    re
/  \
e    r

In above case, since s1 can be generated from str2, that is, str1 can be generated from the partition tree, which has the same leaf of str2, but the order of its child can be switched. So str1 is said to be a scramble string of str2.

A counter example is that Tiger and Tgrie are not scramble string of each other

Question: Given two strings str1 and str2, are they scramble string of each other?

A approach is provided in my previous blog Google Scramble String (I): Without Duplicated characters, however, such approach can only handle the case when there are no duplicated characters in string.

What about the case when a string contains duplicated characters?

Example: A: aabbbaccd,  B: aabcdbcba, are them scramble strings of each other?

It is proposed in this paper a recursive-based Divide-And-Conquer approach, this approach is more efficient than my preivous approaches.

The principle of this approach goes as following
1) Given two strings A and B, try to split each of them into two sub-strings sA1,sA2,sB1, sB2 where sA1 and sB1 are anagrams and sA2 and sB2 are anagrams.
2) If sA1 and sB1 are the scramble strings while sA2 and sBs are scramble strings, then A and B should be scramble strings.
3) Recursivly analyze sA1 and sB1, sA2 and sB2 by start over from step 1).

In previous example

str1 = aabbbaccd, str2: aabcdbcba,

They are split as: (aab)(bbaccd),  (aab)(cdbcba) => compare bbaccd and cdbcba
They are split as: (bbac)(cd),  (cd)(bcba) => compare bbac and bcba
They are split as: (b)(bac), b(cba) => (ba)(c) vs (c)(ba)

They are scramble stromh of each other

// index means how many characters in a new anagram
// direction means the way of split
//example, abcdef and efcabd, then direction = false and index = 2 for "ef"
//example, abcdef and abefcd, then direction = true and index =1 for "a"
public static List<int> stringSplitIndex(char[] chArr1, char[] chArr2, int start1, int end1, int start2, int end2, List<int> indexList, List<bool> directionList)
        {
            int index = 0;
            //two ways of anagram, AB-AB and AB-BA
            Dictionary<char, int>
                headToHeadDict = new Dictionary<char, int>(),
                headToTailDict = new Dictionary<char, int>(); 
            while (start1+index<end1)
            {
                //add value from first string
                if (!headToHeadDict.ContainsKey(chArr1[start1 + index]))
                    headToHeadDict.Add(chArr1[start1 + index], 1);
                else
                {
                    headToHeadDict[chArr1[start1 + index]]++;
                    if(headToHeadDict[chArr1[start1 + index]]==0)
                        headToHeadDict.Remove(chArr1[start1 + index]);
                }
                if (!headToTailDict.ContainsKey(chArr1[start1 + index]))
                    headToTailDict.Add(chArr1[start1 + index], 1);
                else
                {
                    headToTailDict[chArr1[start1 + index]]++;
                    if(headToTailDict[chArr1[start1 + index]]==0)
                        headToTailDict.Remove(chArr1[start1 + index]);
                }
                //delete value from dictionary by the second string
                if (!headToHeadDict.ContainsKey(chArr2[start2 + index]))
                    headToHeadDict.Add(chArr2[start2 + index], -1);
                else
                {
                    headToHeadDict[chArr2[start2 + index]]--;
                    if (headToHeadDict[chArr2[start2 + index]] == 0)
                        headToHeadDict.Remove(chArr2[start2 + index]);
                }
                if (!headToTailDict.ContainsKey(chArr2[end2-index]))
                    headToTailDict.Add(chArr2[end2-index], -1);
                else
                {
                    headToTailDict[chArr2[end2 - index]]--;
                    if (headToTailDict[chArr2[end2 - index]] == 0)
                        headToTailDict.Remove(chArr2[end2 - index]);
                }
                //at this point the strings can be split into two anagrams
                if (headToHeadDict.Count == 0)
                {
                    indexList.Add(index);
                    directionList.Add(true);
                }
                if (headToTailDict.Count == 0)
                {
                    indexList.Add(index);
                    directionList.Add(false);
                }
                index++;
            }

            return indexList;
        }
        public static Boolean googleScrambleStringRecursive(char[] ch1, char[] ch2, int start1, int end1, int start2, int end2)
        {
            if (end1 == start1 && end2 == start2 && ch1[start1] == ch2[start2])
                return true;
            if(end1-start1!=end2-start2)
                return false;
            List<bool> directionList = new List<bool>();
            List<int> indexList = stringSplitIndex(ch1, ch2, start1, end1, start2, end2, new List<int>(),directionList);
            if (indexList.Count==0)
                return false;
            bool isScramble = false;
            for(int i=0;i<directionList.Count;i++)
            {
                if(directionList[i])
                {
                    isScramble =  googleScrambleStringRecursive(ch1, ch2, start1, start1+indexList[i], start2, start2+indexList[i]) &&
                           googleScrambleStringRecursive(ch1, ch2, start1 + indexList[i] + 1, end1, start2 + indexList[i] + 1, end2); 
                    if(isScramble)
                        return isScramble;
                }
                else
                {
                    isScramble = googleScrambleStringRecursive(ch1, ch2, start1, start1 + indexList[i], end2 - indexList[i], end2) &&
                           googleScrambleStringRecursive(ch1, ch2, start1 + indexList[i] + 1, end1, start2, end1 - indexList[i] - 1);
                    if(isScramble)
                        return isScramble;
                }
            }
            return isScramble;
        }

Google Scramble String (II): With Duplicated characters

Scramble string, for two strings, say str1 = “tiger” and str2 = “itreg”
tiger
/    \
ti    ger
/  \   /   \
t    i  g    er
/  \
e    r

itreg
/    \
it     reg
/  \   /   \
t    i  g    re
/  \
e    r

In above case, since s1 can be genrated from str2, that is, str1 can be generated from the partition tree, which has the same leaf of str2, but the order of its child can be switched. So str1 is said to be a scramble string of str2.

A counter example is that Tiger and Tgrie are not scramble string of each other

Question: Given two strings str1 and str2, are they scramble string of each other?

A approach is provided in my previous blog Google Scramble String (I): Without Duplicated characters, however, such approach can only handle the case when there are no duplicated characters in string.

What about the case when a string contains duplicated characters?

Example: str1: aabbbaccd, str2: aabcdbcba, are them scramble strings of each other?

It is proposed in this blog a similar merge and check approach, instead of merge them as integer intervals by their index, we can merge its sub strings.

For string str2: aabcdbcba, we create a stack S1 to stores each of its characters (as a string) while another stack S2 to be the auxiliary stack.

S1:[“a”,”a”,”b”,”c”,”d”,”b”,”c”,”b”,”a”] S2:[]

The algorithm goes as follows:

1) Build two strings comStr1 = S1.peek() + S2.peek() and comStr2 = S2.peek() + S1.peek()
1.1) if str1 contains neither of them, push S1.pop to S2.
1.2) if Str1 contains only one of them, push the combined string to S1. Before the push one needs to first do S1.pop and S2.pop.
1.3) if Str1 contains both of them
1.3.1) if comStr1 == comStr2, then push either combined string to S1. Before the push one needs to first do S1.pop and S2.pop.
1.3.2) if comStr1 != comStr2, then we have two candidates. In this case we need to choose the better one. We try to see if both the candidates can merge with the new S1.Peek() or S2.Peek(). This is a recursive approach. It is very similar to the Step 1) but in this case comStr1 = candidiate+S2.peek(), comStr2 = S2.peek() + candidiate (if neither of them can not merged with S2.peek(), one needs to repeat the process by replacing S2.peek() with s1.peek()). After the comparison, there should be only one candidate left. Then one can push it to S1. There is only one case where both multiple candidates can be observed, that is, all the candidates are the same as the S1, that is the end of the comparison.

2) In the end, that is, when S1 is empty, check if S2 contains only one element.

Let us take the above case as an example:

Iteration 1 starts: S1:[“a”,”a”,”b”,”c”,”d”,”b”,”c”,”b”,”a”] S2:[]
Iteration 1 ends: S1:[“a”,”a”,”b”,”c”,”d”,”b”,”c”,”b”] S2:[a]

Iteration 2 starts : S1:[“a”,”b”,”c”,”d”,”b”,”c”,”b”] S2:[“a”].
Because in this case the combinations of S1.peek() and S2.peek() can be “ab” and “ba” and both strings can be found in str1, we meet the situation of multiple candidates. Therefore, we need to check which one is better.
current Stacks: S1:[“a”,”b”,”c”,”d”,”b”,”c”], S2:[], candidates: “ab” and “ba”
For candidate “ab” neither “abc” nor “cba” can be found in Str1, however, for candidate “ba”, “bac” can be found in Str1, therefore, “ba” is better and we should push “bac” in S1.
Iteration 2 ends: S1:[“a”,”a”,”b”,”c”,”d”,”b”, “bac”] S2:[]

Iteration 3 starts: S1:[“a”,”a”,”b”,”c”,”d”,”b”, “bac”] S2:[]
Iteration 3 ends: S1:[“a”,”a”,”b”,”c”,”d”,”b”] S2:[“bac”]

Iteration 4 starts: S1:[“a”,”a”,”b”,”c”,”d”,”b”] S2:[“bac”]
Iteration 4 ends: S1:[“a”,”a”,”b”,”c”,”d”, “bbac”] S2:[] //only “bbac” can be found in Str1

Iteration 5 starts: S1:[“a”,”a”,”b”,”c”,”d”, “bbac”] S2:[]
Iteration 5 ends: S1:[“a”,”a”,”b”,”c”,”d”] S2:[“bbac”]

Iteration 6 starts: S1:[“a”,”a”,”b”,”c”,”d”] S2:[“bbac”]
Iteration 6 ends: S1:[“a”,”a”,”b”,”c”] S2:[“d”,”bbac”] //neither “dbbac” nor “bbacd” can be found in Str1

Iteration 7 starts: S1:[“a”,”a”,”b”,”c”] S2:[“d”,”bbac”]
Iteration 7 ends: S1:[“a”,”a”,”b”,”cd”] S2:[“bbac”] //only “cd” can be found in Str1

Iteration 8 starts: S1:[“a”,”a”,”b”,”cd”] S2:[“bbac”]
Iteration 8 ends: S1:[“a”,”a”,”b”,”bbaccd”] S2:[] //only “bbaccd” can be foudn in Str1

Iteration 9 starts: S1:[“a”,”a”,”b”,”bbaccd”] S2:[]
Iteration 9 ends: S1:[“a”,”a”,”bbbaccd”] S2:[]

Iteration 10 starts: S1:[“a”,”a”,”bbbaccd”] S2:[]
Iteration 10 ends: S1:[“a”,”abbbaccd”] S2:[]

Iteration 11 starts: S1:[“a”,”abbbaccd”] S2:[]
Iteration 11 ends: S1:[“aabbbaccd”] S2:[]

Iteration 12 starts: S1:[“aabbbaccd”] S2:[]
Iteration 12 ends: S1:[] S2:[“aabbbaccd”]

Since only one element in S2, they are scramble strings of each other.

public static Boolean googleScrambleStringWithDuplication(string s1, string s2)
{
    Stack<string> stack1 = new Stack<string>(), stack2 = new Stack<string>();
    for (int i = 0; i < s2.Length; i++)
        stack1.Push(Convert.ToString(s2[i]));
    List<string> availableStrList = new List<string>();
    while (stack1.Count > 0)
    {
        availableStrList.Add(stack1.Pop());
        List<string> combinedStrList = new List<string>();
        //extend the string from Stack2
        while (stack2.Count > 0)
        {
            foreach (string str in availableStrList)
            {
                if(s1.Contains(str + stack2.Peek())&&!combinedStrList.Contains(str + stack2.Peek()))
                    combinedStrList.Add(str + stack2.Peek());
                if(s1.Contains(stack2.Peek()+str)&&!combinedStrList.Contains(stack2.Peek()+str))
                    combinedStrList.Add(stack2.Peek()+str);
            }
            if (combinedStrList.Count == 0)
                break;
            else
            {
                stack2.Pop();
                availableStrList = combinedStrList;
                combinedStrList = new List<string>();
            }
        }
        //When we have multiple candidates
        while (availableStrList.Count > 1)
        {
            //checking which one is better by extending from Stack1
            while (stack1.Count > 0)
            {
                foreach (string str in availableStrList)
                {
                    if (s1.Contains(str + stack1.Peek()) && !combinedStrList.Contains(str + stack1.Peek()))
                        combinedStrList.Add(str + stack1.Peek());
                    if (s1.Contains(stack1.Peek() + str) && !combinedStrList.Contains(stack1.Peek() + str))
                        combinedStrList.Add(stack1.Peek() + str);
                }
                if (combinedStrList.Count == 0)
                    break;
                else
                {
                    stack1.Pop();
                    availableStrList = combinedStrList;
                    combinedStrList = new List<string>();
                }
            }
        }
        stack2.Push(availableStrList[0]);
        availableStrList = new List<string>();
    }
    return stack2.Count == 1;
}

Find K nodes in BST that are closest to a value key (Part II).

Question: There is a BST while each node has distinct values, then for a given value key, find out K nodes in this BST such that their values are closest to key.

Solution:

It is provided in previous blog Find K nodes in BST that are closest to a value key (Part I) an O(log(n)) approach to find out such K nodes, however previously is was assumed that each node in BST has “Parent” pointer, what if this pointer is unavailable? Furthermore, some one may argue that in order to find out is next larger node or next smaller node, one sometimes needs to back track through the entire tree path, and which takes O(log(n)) time and therefore not efficient.

Hence, this blog provide an O(log(n)) approach without the help of the “Parent” pointers. It uses extra addition space to store a stack, which stores all the parent nodes when travelling at a given node. An auxiliary reading about how to use stack to iteratively traverse the BST can be found in http://www.leetcode.com/2010/04/binary-search-tree-in-order-traversal.html.

The algorithm can go as following:

1) Start from the root node to find out the node (denoted as the closestNode) whose value is closest to key, store all the passed middle-level nodes in a stack where stack.peek() is the closeNode. In this case, the return value should be a stack instead of a single node.
2) Generate two functions the nextLargerNodeInBSTIterative() and nextSmallerNodeInBSTIterative(), by the help of the stack and based on closestNode find its next larger node, denoted as nextLarger, and find its next smaller node, denoted as nextSmaller.
3) Compare nextSmaller to nextLarger by their difference to key, and update them appropriately until K nodes are selected.

Step 1) costs O(log(n)), with space complexity O(log(n)).
Step 3) In the worse case, it takes O(log(n)) to find its next larger node or its next smaller node, however, each node in BST is check at most once. Therefore the time complexity should be max{O(log(n)), O(K)} = O(log(n)).

Overall, its an O(log(n)) approach.

//main function, for step 3)
public static List findKClosestNodeInBSTIterative(Tree root, int key, int k)
{
    List list = new List();
    Stack stack = findTreeWithKeyNearestToTheKeyIterative(root, key);
    Tree closestNode = stack.Pop();
    k--;
    list.Add(closestNode);
    Stack stackForSmaller = new Stack(), stackForGreater = new Stack(), temp = new Stack();
    //copy the current stack to two stacks
	//so they can be used in findnext functions.
	while (stack.Count > 0)
        temp.Push(stack.Pop());
    while (temp.Count > 0)
   {
        Tree tempTree = temp.Pop();
        stackForSmaller.Push(tempTree);
        stackForGreater.Push(tempTree);
    }
    Tree nextlarger = nextLargerNodeInBSTIterative(closestNode,stackForGreater);
    Tree nextSmaller = nextSmallerNodeInBSTIterative(closestNode,stackForSmaller);
    while (k > 0)
    {
        if (nextlarger == null && nextSmaller == null)
            throw new StackOverflowException();
        else if (nextlarger != null && nextSmaller != null)
        {
            if (Math.Abs(nextlarger.node - key) >= Math.Abs(nextSmaller.node - key))
            {
                list.Add(nextSmaller);
                k--;
                nextSmaller = nextSmallerNodeInBSTIterative(nextSmaller, stackForSmaller);
            }
            else
            {
                list.Add(nextlarger);
                k--;
                nextlarger = nextLargerNodeInBSTIterative(nextlarger, stackForGreater);
            }
        }
        else if (nextlarger != null)
        {
            list.Add(nextlarger);
            k--;
            nextlarger = nextLargerNodeInBSTIterative(nextlarger, stackForGreater);
        }
        else
        {
            list.Add(nextSmaller);
            k--;
            nextSmaller = nextSmallerNodeInBSTIterative(nextSmaller, stackForSmaller);
        }
    }
    return list;
}

 public static Stack findTreeWithKeyNearestToTheKeyIterative(Tree root, int key)
{
    Stack stack = new Stack();
    Tree desiredRoot = root;
    int diff = Math.Abs(root.node - key);
    while (root != null)
    {
        stack.Push(root);
        if (diff > Math.Abs(root.node - key))
        {
            diff = Math.Abs(root.node - key);
            desiredRoot = root;
        }
        if (root.node > key)
            root = root.leftChild;
        else if (root.node < key)
            root = root.rightChild;
        else
            return stack;
    }
    while (stack.Peek() != desiredRoot)
        stack.Pop();
    return stack;
}

//step 2) find its next larger node
 public static Tree nextLargerNodeInBSTIterative(Tree current, Stackstack)
{
    if (current.rightChild != null)
    {
        Tree nextTree = current.rightChild;
        while (nextTree.leftChild != null)
        {
            stack.Push(nextTree);
            nextTree = nextTree.leftChild;
        }
        return nextTree;
    }
    else
    {
        if (stack.Count > 0)
        {
            Tree tempTree = stack.Pop();
            while (tempTree != null)
            {
                if (tempTree.node > current.node)
                    break;
                else
                    tempTree = stack.Count > 0 ? stack.Pop() : null;
            }
            return tempTree;
        }
        else
            return null;
    }
}
//step 2) find its next smaller node
public static Tree nextSmallerNodeInBSTIterative(Tree current, Stack stack)
{
    if (current.leftChild != null)
    {
        Tree nextTree = current.leftChild;
        while (nextTree.rightChild != null)
        {
            stack.Push(nextTree);
            nextTree = nextTree.rightChild;
        }
        return nextTree;
    }
    else
    {
        if (stack.Count > 0)
        {
            Tree tempTree = stack.Pop();
            while (tempTree != null)
            {
                if (tempTree.node < current.node)
                   break;
                else
                   tempTree = stack.Count>0?stack.Pop():null;
            }
            return tempTree;
        }
        else
            return null;
    }
}

Find K nodes in BST that are closest to a value key (Part I).

Question:

There is a BST while each node has distinct values, then for a given value key, find out K nodes in this BST such that their values are closest to key.

Solution:

It seems to be a very easy question, all we need to do is to do a pre-order traversal and store all the nodes in this BST to an array, and then find out the K numbers that are the nearest to key. However, This approach takes O(n) time.

It is introduced in this blog an O(log(n)) approach with the assumption that the node in BST has “Parent” pointer.

The algorithm can go as following:

1) Start from the root node to find out the node (denoted as the closestNode) whose value is the closest to key.
2) Generate two functions the nextLargerNodeInBST() and nextSmallerNodeInBST(), using which to find the next larger node of the closestNode, denoted as nextLarger, and find its next smaller node, denoted as nextSmaller.
3) Compare nextSmaller to nextLarger by their difference to key, and update them appropriately until K nodes are selected.

Step 1) costs O(log(n)).
Step 3) It takes at most O(log(n)) to find out next point, and each node in BST is checked at most twice in the entire searching, therefore, the overall time complexity is max {O(K), O(log(n))} = O(log(n))

To sum up, it’s an O(log(n)) approach.

// Main Test Function, step 3)
public static List<Tree> findKClosestNodeInBST(Tree root, int key, int k)
{
    List<Tree> list = new List<Tree>();
    Tree closestNode = findTreeWithKeyNearestToTheKey(root, key);
    k--;
    list.Add(closestNode);
    Tree nextlarger = nextLargerNodeInBST(closestNode);
    Tree nextSmaller = nextSmallerNodeInBST(closestNode);
    while (k > 0)
    {
        if (nextlarger == null && nextSmaller == null)
            throw new StackOverflowException();
        else if (nextlarger != null && nextSmaller != null)
        {
            if (Math.Abs(nextlarger.node - key) >= Math.Abs(nextSmaller.node - key))
            {
                list.Add(nextSmaller);
                k--;
                nextSmaller = nextSmallerNodeInBST(nextSmaller);
            }
            else
            {
                list.Add(nextlarger);
                k--;
                nextlarger = nextLargerNodeInBST(nextlarger);
            }
        }
        else if (nextlarger != null)
        {
            list.Add(nextlarger);
            k--;
            nextlarger = nextLargerNodeInBST(nextlarger);
        }
        else
        {
            list.Add(nextSmaller);
            k--;
            nextSmaller = nextSmallerNodeInBST(nextSmaller);
        }
    }
    return list;
}

//find out the node that is closed to the key, step 1)
public static Tree findTreeWithKeyNearestToTheKey(Tree root, int key)
{
    Tree desiredRoot = root;
    int diff = Math.Abs(root.node - key);
    while (root != null)
    {
        if (diff > Math.Abs(root.node - key))
        {
            diff = Math.Abs(root.node - key);
            desiredRoot = root;
        }
        if (root.node > key)
            root = root.leftChild;
        else if (root.node < key)
            root = root.rightChild;
        else
            return root;
        }
    return desiredRoot;
}

//step 2) find its next larger node in BST
public static Tree nextLargerNodeInBST(Tree current)
{
    if (current.rightChild != null)
    {
        Tree nextTree = current.rightChild;
        while (nextTree.leftChild != null)
            nextTree = nextTree.leftChild;
        return nextTree;
    }
    else
   {
        while (current.parentTree!=null)
        {
            if (current != current.parentTree.rightChild)
                return current.parentTree;
            else
            {
                while(current.parentTree!=null&&current==current.parentTree.rightChild)
                    current = current.parentTree;
                return current.parentTree;
            }
        }
        return null;
    }
}

//step 2) find its next smaller node in BST
public static Tree nextSmallerNodeInBST(Tree current)
{
    if (current.leftChild != null)
    {
        Tree nextTree = current.leftChild;
        while (nextTree.rightChild != null)
            nextTree = nextTree.rightChild;
        return nextTree;
    }
    else
    {
        while (current.parentTree != null)
        {
            if (current == current.parentTree.rightChild)
                return current.parentTree;
            else
           {
                while (current.parentTree != null && current == current.parentTree.leftChild)
                    current = current.parentTree;
                return current.parentTree;
            }
        }
        return null;
    }
}

Deserialize integer string to character strings

Question: Suppose we map character to integer in the way that ‘a’ to 1, ‘b’ to 2 and ‘z’ to 26, then given an integer string, how many distinct character strings can we have?

For example: “111” can be converted to: aaa, ak, ka. “110” can only be converted to aj. While “200” or “30” are invalid input strings.

P.S: Some one was asked this question in a Google interview, this guy provided both a recursive approach and a DP approach but still be rejected…How crazy is that? I think we should have our fingers crossed in the interview and pray for the interviewer is not too picky……

Solution:

The following cases need to be exam carefully:
1) When one goes from “11” to “111”, there are more distinct character strings generated, however, when one goes from “11” to “110”, fewer distinct characters strings can be observed.
2) One needs to check the invalid inputs such as “00”,”30″,”40″….”90″.

Recursive Approach

This approach jumped out when I first saw this question, the idea is simple, one goes through each entry of the integer string, and go to different branches according to the values of its neighbor entries. One should be extremely careful about the bounder conditions.

Since it is a recursive approach, the time complexity may not be satisfactory, besides, the code is lengthy….I tried to implement it efficiently but still need around 40 lines….

A sample code is provided as below. The hashtable stores all the mappings, the allList and list are initially set to empty list.

some test cases are:

deserializeTheNumericStringRecursive(“21220”.ToCharArray(), 0, ad.dictNumToChar, allList, list);

“3502034” (invalid), “210220612”, “2010220”, “10”, “11”, “1”, “01”

DP approach:

We are going to use an auxiliary integer array count[] to store how many distinct character strings we can obtain upto this entry.

count[0] and count[1] should be identified before the DP.

From count[2] to count[n], the value of count[i] can be determined by the values of the count[i-1] and count[i-2].

How? Let us see the following examples:

charArr = “2123”, count[] = {1,2,?,?}, since charArr[2] = ‘2’. It can be converted to ‘b’ itself or can be converted to ‘l’ as part of the ’12’. The characters in similar cases are called the “Tricky number”. Therefore, very similar to the famous Fibonacci number, we can get the count[2] = count[1] + count[0].

The meaning of such equation is: attach ‘2’ to the distinct character strings obtained in its latest entry, that is to add the count[1]. Or instead, one can also attach ’12’ to the distinct character strings obtained from the second latest entry, that is to add the count[0].

In the same manner, the fourth entry of the charArr is also a tricky number. One can attach the ‘3’(c) to the latest distinct character strings, or attach ’13′(m) to the second latest distinct character string. Therefore, for a string “2123”, the correspond count[] = {1,2,3,5} and one should return 5.

Be careful about the case of “2120”, as initial count to be count[] = {1,2,?,?}, in the third entry, the character ‘2’ is no longer a tricky number, since it has to be part of the ’20’ to make the input string valid.

Here comes the definitions of the tricky number:

For a entry i, charArr[i] is a tricky number if and only if the following cases are true:

1) temp = charArr[i-1]*10 +charArr[i-1], temp should be between 11 and 26 and can not be 20.

2) charArr[i+1] can not be ‘0’.

If the charArr[i] is not a tricky number, then count[i] = count[i-1];

//The Recursive approach
public static List<List<char>> deserializeTheNumericStringRecursive(char[] chArr, int index,    Dictionary<int,char>dict,List<List<char>> allList, List<char>list)
{
   if (index >= chArr.Length)
   {
     allList.Add(list);
     return allList;
    }
   else if (index == chArr.Length - 1 && chArr[index] != '0')
   {
      list.Add(dict[chArr[index] - '0']);
       return deserializeTheNumericStringRecursive(chArr, index + 1, dict, allList, list);
   }
   else
   {
     //happens when string contains "00,30,40,...90" or starts with '0'
     if (chArr[index] == '0')
         throw new Exception();
     else if ((chArr[index] == '1' || chArr[index] == '2') && chArr[index + 1] == '0')
     {
         list.Add(dict[(chArr[index] - '0') * 10 + chArr[index + 1] - '0']);
         return deserializeTheNumericStringRecursive(chArr, index + 2, dict, allList, list);
     }
     //No tricky numbers
     else if (chArr[index] - '0' > 2 || (chArr[index] - '0' == 2 && chArr[index + 1] - '0' > 6))
     {
         list.Add(dict[chArr[index] - '0']);
         return deserializeTheNumericStringRecursive(chArr, index + 1, dict, allList, list);
     }
     else
     {
        //Tricky numbers
        if (index + 2 == chArr.Length || chArr[index + 2] != '0')
        {
            List<char> list1 = new List<char>(), list2 = new List<char>();
            list1.AddRange(list); list2.AddRange(list);
            list1.Add(dict[chArr[index] - '0']);
            list2.Add(dict[(chArr[index] - '0') * 10 + chArr[index + 1] - '0']);
            allList = deserializeTheNumericStringRecursive(chArr, index + 1, dict, allList, list1);
            allList = deserializeTheNumericStringRecursive(chArr, index + 2, dict, allList, list2);
           return allList;
        }
        else
        {
           list.Add(dict[chArr[index] - '0']);
           return deserializeTheNumericStringRecursive(chArr, index + 1, dict, allList, list);
         }
      }
   }
}

//The DP approach
public static int deserializeTheNumericStringDP(char[] chArr)
{
   if (chArr.Length == 0) return 0;
   if (chArr.Length == 1) return chArr[0] == '0' ? 0 : 1; 
   int[] count = new int[chArr.Length];
   if (chArr[0] == '0') return 0;
   count[0] = 1; 
   int temp = (chArr[0] - '0') * 10 + (chArr[1] - '0');
   if (temp == 10 || temp == 20 || temp > 26 || (chArr.Length>2&&chArr[2]=='0'))
        count[1] = 1;
   else
        count[1] = 2;
   for (int i = 2; i < chArr.Length; i++)
   {
       temp = (chArr[i-1]-'0')*10+chArr[i]-'0';
       if(temp%10==0&&(temp>20||temp==0))
           throw new Exception();
       if (temp > 11 && temp < 26 && temp != 20 && (i==chArr.Length-1||chArr[i+1]!='0'))
            count[i] = count[i - 1] + count[i - 2];
       else
            count[i] = count[i - 1];
    }
   return count[count.Length - 1];   
}

Number of ways to print the distinct representations of 2^n

I posted a solution to find out the number of distinct representation of 2^n. However, recently I found that is not the optimum one, thanks to “CAIWU”, who inspired me that this is eventually a unique sum-to-target problem and usually can be done by recursive approach.

Let us start with the question recall:

Given a number n, find out the number of distinct representations of 2^n.

Example: n = 3, there are three distinct representations of 2^3 = 8 as 2*2*2, 2*4, 8*1. Noticed that in this case, 4*2 is the same as the 2*4.

Another example when n=5, there are seven distinct representations for 2^5 = 32, those are: 2*2*2*2*2, 2*2*2*4, 2*2*8, 2*16, 2*4*4, 4*8, 32*1.

I have to say, in the beginning I have no clue about how to get such representations. The first idea in my head is to find out all the combinations and put them into a hashtable. However, that is so time consuming and when n grows large, for example n=1500, there are too many duplications and by multiplication 2^1500 is beyond Integer or even long, it is easily to get stackOverflow or some other related exceptions.

Inspired by CaiWu, this problem can be converted to the following one:

Given a number of n, from 1 to n, find out different summations that add up to n.

This is really a brilliant idea, first of all, now we have the range of n instead of 2^n, which means in most of the cases the representations can be present by integers. Secondly, by recursive approach we do not need to worry about the duplications.

Examples:

When n = 3, the previous representations  2*2*2, 2*4, 8*1,can now be converted to 1+1+1, 1+2, 3+0 (3).

When n = 5, the previous representations 2*2*2*2*2, 2*2*2*4, 2*2*8, 2*16, 2*4*4, 4*8, 32*1 can now be converted to 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+4, 1+2+2, 2+3, 5+0.

As one can observe from these representations, for a given n, we only need to go through every entry from 1 to n, and based on each entry to do recursively adding.

The code listed below is a recursive approach to find such summations. Let us use n=5 as an example:

Parameters:
Target: the value of n, in this example, Target is 5.
CurrentSum: the current sum in each iteration, it is initially set to 0.
CurrentIndex: We start at 1, so CurrentIndex is initially set to 1, it is always increase in the sample code, therefore no duplications will be generated.
allList: A list contains all possible representations, it is initially empty.
list: A list contains the up-to-now candidates, it is initially empty

//(5,0,1,new List<List<int>>(), new List<int>())
public static List<list> distinceRepresentationsOfProductOf2(int target, int currentSum,  int currentIndex, List<list>allList, Listlist)
{
    if (currentSum == target)
    {
       List validPath = new List();
       validPath.AddRange(list);
       allList.Add(validPath);
       return allList;
    }
    else
    {
       if (currentSum + currentIndex > target)
          return allList;
       else
       {
           for (int i = currentIndex; i <= target; i++)
           {
               list.Add(i);
               allList = distinceRepresentationsOfProductOf2(target, currentSum + i, i, allList, list);
               list.RemoveAt(list.Count - 1);
            }
            return allList;
       }
    }
}