Twenty Percent Knowledge

Monday, July 06, 2015

String Permutation

Problem:

Given a string, return all possible permutations of its characters.

Analysis:

If repeated characters can take only one chance to take part in the permutation, you can put all the characters in a set the first, then following the same idea showing here to work with a set.

This is P(n,n) = n!
(P.S. P(n, r) = n(n − 1)...(n − r + 1))

The first place, you can pick from n number of characters, the second place has n-1 character to choose from, so on so forth, until n-1 has one characters to choose from and n has no character to choose from.

This can be done naturally by recursive algorithm. Say f(s) is a function to return all permutation of a string, From left to right, the result would be s(i)+permutation of rest of characters:
s(i)+f(s without s(i))

Recursive implementation

Note: just found it's similar to perm1 in http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html

 public static List<String> stringPermutation(String s){
  if (s==null)return null;
  if (s.length()==1){
   List<String> l =new LinkedList<String>();
   l.add(s);
   return l;
  }
  List<String> result = new LinkedList<String>();
  for(int i=0;i<s.length();i++){
   List<String> subStrings = stringPermutation(s.substring(0,i)+s.substring(i+1));
   if (subStrings!=null)
    for(String o:subStrings)
     result.add(s.charAt(i)+o);
  }
  return result;
 }

Iterative Implementation

Using a queue to dynamically further building the result: a queue contains first set of result, the result will be further processed and become next set of result, on and on until the result set is good.

public static List<String> stringPermutationIter(String s){
  if (s==null)return null;
  //temporary variable for each substring that can be concatenated further with pickable characters
  String tmp;
  //condition to control when to stop
  boolean isToContinue = true;
  //a queue that contains result, it's content will be dynamically taken out and added in after further processing, 
  //such as combining with other characters
  LinkedList<String> finished = new LinkedList<String>();
  //original set that can be used to work out subset that does not contain the character already included in string built out
  LinkedList<Character> wholeSet = new LinkedList<Character>();
  //subset that does not contain the character already included in string built out
  LinkedList<Character> toBeProcessed = new LinkedList<Character>();
  //initialize the wholeset and finished
  for (int i=0;i<s.length();i++){
   wholeSet.add(s.charAt(i));
   //starting from one character which is every character in the given string
   finished.add(String.valueOf(s.charAt(i)));
  }
  

  while(isToContinue){
   tmp = finished.remove();//pop out the first string that is waiting for furthe process
   //stop adding new element when it find item's length is the same as original string
   //put the object back to queue since that is valid one
   if (tmp.length()==s.length()){
    isToContinue=false;
    finished.add(tmp);
   }
   
   toBeProcessed.clear();
   toBeProcessed.addAll(wholeSet);
   //this (remove) works for string containing only distinct characters
   for(int i=0;i<tmp.length();i++)
    //removeFirstOccurrence works with all kind of strings including a string with repeated characters
    toBeProcessed.removeFirstOccurrence((Character)tmp.charAt(i));
   for(Character c: toBeProcessed)
    finished.add(tmp+c);
   
  }
  return finished;
 }

Thursday, July 02, 2015

Tell if a List is a subset of another List

Problem:
two sorted list, please tell if one contains another.

Solutions:
1. Cheating: using Java's containsAll function in List
2. Seriously, this concept should be applied to other type of "list", such as array.

Analysis:
Do not mix this up with substring problem. In substring, all elements have to be adjacent. in this problem, it only cares if one contains another.

2.1 sort the list the first, then from there, find each element in subset in list that is searched on.

 public static boolean isSubset(List<Integer> first, List<Integer> subset){
       if (subset==null)return true;
       if (first ==null) return false;

       int sCursor = 0;
       int fCursor = 0;
      
       while(sCursor<subset.size() && fCursor<first.size()){
        if (first.get(fCursor)>( subset.get(sCursor)))
          return false;
        else if (first.get(fCursor)<( subset.get(sCursor)))
          fCursor++;
 //then there is an equal.
        else{

//try to work on next element in subset,for that element, keep increasing/searching

//cursor in super set to find a match
          sCursor++;

        }
       }
       if (sCursor==subset.size())
         return true;
      
       return false;
 }

2.2 how to do it if lists are not sorted.
Well we can sort them and then use 2.1. But let's be realistic and have a real solution.
Off top of my head, we can loop through subset, for each one of elements, search it in searched list. O(m8n)==O(n^2) time. Naive but should work. I like the sorting idea.

A little bit improving, let's sort the list to be searched, then keeping the first loop of subset, using binary search on sorted searched list. It'd be O(nlogn), still worse then 2.1, but better than first solution in 2.2

3. Resort to a Hashset
put elements in list to be searched to hashset, do not bother to store the duplicated values.
then loop through searching list to see if every element is in the hashset. return false if not in hashset, otherwise, after looping, return true. still linear time, but more space. This does not require the list to be sorted. and it more common solution to this kind of problems.

public static boolean isSubsetCommon2(int[] first, int[] subset){
    if (subset==null)return true;
    if (first ==null) return false;
    Set<Integer> superSet = new HashSet<Integer>();
    //this can be wirtten as a for loop to add array elements to set
    
    for(int i=0;i<first.length;i++){
     superSet.add(first[i]);
    }
    for (Integer o:subset){
     if (!superSet.contains(o))return false;
    }
    return true;
}

4. brute force approach
loop collection to search in
loog collection of subset
if there is a match, break
if reaching to end of subset, means no matching, return false
reach this point, return true

O(m*n)

Tuesday, June 30, 2015

Longest Common Substring

First method returns length of longest common substring.
Second method is modified based on first method to return the longest common substring.

It's interesting to see the two solutions coming out one year apart.

Second version: done in 2016. I am not improved :)

import java.util.Objects;

/**
 * converting it to 2d array, x coordination is from one string and y coordination is form another string.
 * the matching substrings will be adjacent diagonal sequences. 
 * this way is also easy to retrieve all the common substrings: stating from 1 and diagonally increasing
 * advanced and more efficient way: suffix tree
 * @author Andrew Ma
 *
 */
public class LongestCommonSubString {
 public static int longestCSLength(String s1, String s2){
  /**
   * s1 is y, vertical. s2 is x, horizontal
   */
  Objects.requireNonNull(s1);
  Objects.requireNonNull(s2);
  int maxLength = 0;
  if(s1.length()==0 ||s2.length()==0)return 0;
  char[] s1y = s1.toCharArray();
  char[] s2x = s2.toCharArray();
  int[][] matches = new int[s1.length()][s2.length()]; 
  for(int x=0;x<s2.length();x++){
   for(int y=0;y<s1.length();y++){
    //mark and count
    if(s2x[x]==s1y[y]){
     if(x==0 || y==0){//on top or left boarder, start as 1
      matches[y][x]=1;
     }else{
     matches[y][x] = matches[y-1][x-1]+1;
     }
     maxLength = Math.max(matches[y][x],maxLength);
    }
    else
     matches[y][x]=0;
   }
  }
  return maxLength;
 }
 public static String retrieveString(String s1,String s2, int s1P,int s2P){
  StringBuffer sb = new StringBuffer();
  while(s1P>=0 && s2P>=0&&s1.charAt(s1P)==s2.charAt(s2P)){
   sb.append(s1.charAt(s1P));
   s1P--;
   s2P--;
  }
  return sb.reverse().toString();
 }
 public static String longestCommonSubstring(String s1, String s2){
  /**
   * s1 is y, vertical. s2 is x, horizontal
   */
  Objects.requireNonNull(s1);
  Objects.requireNonNull(s2);
  String longestSubStr = "";
  int maxLength = 0;
  if(s1.length()==0 ||s2.length()==0)return "";
  char[] s1y = s1.toCharArray();
  char[] s2x = s2.toCharArray();
  int[][] matches = new int[s1.length()][s2.length()]; 
  for(int x=0;x<s2.length();x++){
   for(int y=0;y<s1.length();y++){
    //mark and count
    if(s2x[x]==s1y[y]){
     if(x==0 ||y==0){//on top or left boarder, start as 1
      matches[y][x]=1;
     }else{
     matches[y][x] = matches[y-1][x-1]+1;
     }
     if(maxLength <matches[y][x]){
      maxLength = matches[y][x];
      longestSubStr = retrieveString(s1,s2,y,x);
     }
    }
    else
     matches[y][x]=0;
   }
  }
  return longestSubStr;
 }
 public static void main(String[] args){
  int i = longestCSLength("abcdefg","uiubciabcdu");
  System.out.println(i);
  String s = longestCommonSubstring("abcdefg","uiubciabcdu");
  System.out.println(s);
 }
}

First version in 2015.

public class longestCommonSubstr {

 public static void main(String[] args) {
  System.out.println(longestCommonStrLen("aaabbbccc",
    "hshshsabbbcklklkl"));

 }

 public static int longestCommonStrLen(String first, String second) {
  if (first == null || second == null || first.length() == 0
    || second.length() == 0) {
   return 0;
  }
  // a variable to hold the maximum length
  int maxLen = 0;
  // imaging first is listed vertically, each character marks a row
  /**
   * abc
   *a
   *b
   *c
   */
  int row = first.length();
  // imaging second is listed horizontally
  // bcd
  /**
   * together a matric is like this bcd a b 1 c 2 for a matrix like that,
   * if there is a common substring, you will find both dimensions will
   * grow together
   */
  int column = second.length();
  int[][] table = new int[row][column];
  // initialize first row values to be 0
  for (int s = 0; s < column; s++)
   table[0][s] = 0;
  // initialize first column values to be 0
  for (int f = 0; f < row; f++)
   table[f][0] = 0;

  for (int i = 0; i < row; i++) {
   for (int j = 0; j < column; j++) {

    // at current position, it checks previous position's value.
    // common substring means both dimensions grow at same time. the
    // calculation is from low to high, so that in order to
    // determine higher position's length,
    // it need to figure out lower position's length the first
    // for edge matches,it starts with 1, means one match
    if (first.charAt(i) == second.charAt(j)) {

     // starting from edges, initialize count to be 1
     if (i == 0 || j == 0) {
      table[i][j] = 1;
     } else {
      table[i][j] = table[i - 1][j - 1] + 1;
     }
     if (table[i][j] > maxLen) {
      maxLen = table[i][j];
     }
    }
   }
  }
  return maxLen;
 }

 public static String getLongestCommonSubstr(String first, String second) {
  if (first == null || second == null || first.length() == 0
    || second.length() == 0) {
   return "";
  }
  // a variable to hold the maximum length
  StringBuilder sb = new StringBuilder();
  int maxLen = 0;
  // one position in one string is enough
  int maxI = 0;
  // imaging first is listed vertically, each character marks a row
  /**
   * abc
   *a
   *b
   *c
   */
  int row = first.length();
  // imaging second is listed horizontally
  // bcd
  /**
   * together a matrix is like this bcd a b c for a matrix like that, if
   * there is a common substring, you will find both dimensions will grow
   * together
   */
  int column = second.length();
  // do not need to have an extra column and row, this matrix represents
  // all possible matching points, it's value is length of
  // substring as result of growing diagonally
  int[][] table = new int[row][column];
  // initialize first row values to be 0, set it to 1 when there is a
  // match
  for (int s = 0; s < column; s++)
   table[0][s] = 0;
  // initialize first column values to be 0, set it to 1 when there is a
  // match
  for (int f = 0; f < row; f++)
   table[f][0] = 0;
  // traversal the two strings. it check back both dimensions to determine
  // if substring grows
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < column; j++) {

    // at current position, it checks previous position's value.
    // common substring means both dimensions grow at same time. the
    // calculation is from low to height, so that in order to
    // determine higher position's length,
    // it need to figure out lower position's length the first
    // for edge matches,it starts with 1, means one match
    if (first.charAt(i) == second.charAt(j)) {

     // starting from edges, initialize count to be 1
     if (i == 0 || j == 0) {
      table[i][j] = 1;
     }
     // other wise, substring is growing, mark the length and
     // build it out
     else {
      table[i][j] = table[i - 1][j - 1] + 1;

     }
     if (table[i][j] > maxLen) {
      maxLen = table[i][j];
      maxI = i;
     }
    }
   }
  }
  while (maxLen > 0) {
   sb.append(first.charAt(maxI - maxLen + 1));
   maxLen--;
  }
  return sb.toString();
 }
}

Monday, June 29, 2015

Bit Operation Review

And (&):	0 & 0 = 0	1 & 0 = 0	0 & 1 = 0	1 & 1 = 1
Or (\|):	0 \| 0 = 0	1 \| 0 = 1	0 \| 1 = 1	1 \| 1 = 1
Xor (^):	0 ^ 0 = 0	1 ^ 0 = 1	0 ^ 1 = 1	1 ^ 1 = 0

Left Shift:

x << y means x shifted y bits to the left. If you start shifting and you run out of space, the bits just “drop off”. For example:
00011001 << 2 = 01100100
00011001 << 4 = 10010000

Right Shit
x >> y means x shifted y bits to the right. If you start shifting and you run out of space, the bits just “drop off” the end. Example:
00011001 >> 2 = 00000110
00011001 >> 4 = 00000001

((n & (n-1)) == 0) checks if n is a power of 2 (or 0).

XOR
one number, when XOR with another number twice, it turns back to itself again.
e.g. 1000^0101=1101, 1101^0101=1000 that is a^b and ^b again to get back a. similarly, a^b and ^a again to get b. with this feature, you can swap two number by using XOR operations
a=a^b;
b=a^b;//b now is a
a=a^b;//this equivalent to a^b^a=b
(XOR with same number twice equals not applying anything)

Saturday, June 27, 2015

Decode Ways

Question
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

My Answer:

/**
 * analysis:
 * I thought it is multiplication, then since it adds up conditionally, so better 
 * go with basic addition
 * 1. the numbers that can have two meanings
 * 22, {BB,W}
 * 222, {BBB,BW,WB}
 * ~~~position i-2+22 or i-1+2 when i-1 and i compose a number between 11 and 26 (except 20)
 * 2222, {BBWW,WW,(up to here is position i-1 to current position)BBBB,BWB,WBB(these three are transitioning from position i-1)}
 * 22222 this would be all ways from position i-1 and i-2 if last number has position i
 * so general formular ways[i]=ways[i-1+ways[i-2]
 * it is possible to start from two previous position to transit to current position, because number here is just either 1 digit or 2 digits
 * 
 * 2.if a position has number bigger than 2, then there is only one way to map back to letter
 * 2234
 * 34 is not possible, so it has to be 223(remains all possible combinations) and 4, equivalent to number of ways of 223
 * here i0=1,i1=2,i2=3, i3 is still 3
 * 
 * 3. 0
 * leading 0 is impossible and means wrong input, return 0. mainly because the map has no 0 in it
 * 0,00, 30, 301(30,1 or 3,01 are all invalid)
 * 
 * @author Andrew
 *
 */
public class Solution {

 public static int numDecodings(String s) {
  ///"","0","00", leading with 0
  if (s == null || s.length() == 0 || "0".equals(s.substring(0, 1))) {
   return 0;
  }
  //2,08
  if (s.length() == 1) return 1;

  int[] ways = new int[s.length()];
  char prevChar, curChar;
  int curNum;

  ways[0] = 1;
  ways[1] = 1;
  //for string longer than 2, figure out the first 2 positions possible combinations
  //this might be able to be integrated to the following loop
  if (s.length() >= 2) {
   //impossible situations: 30, 40, only 0 has this problem because it is not in the map
   if (s.charAt(0) > '2' && s.charAt(1) == '0') ways[1] = 0;
   //10 and 20 are valid, and they has only one possible decoding way
   else if ((s.charAt(0) == '1' || s.charAt(0) == '2') && s.charAt(1) == '0') ways[1] = 1;
   //all other numbers such as 11,22 26 are having 2 possible decodings
   else if (Integer.parseInt(s.substring(0, 2)) > 10 && Integer.parseInt(s.substring(0, 2)) <= 26) ways[1] = 2;
  }
  //starting form third position because my basic assumption is ways[i]=ways[i-1]+ways[i-2]
  for (int i = 2; i < s.length(); i++) {
   prevChar = s.charAt(i - 1);
   curChar = s.charAt(i);
   curNum = Integer.parseInt("" + prevChar + curChar);
   //for 20 and 10(0 is position i),i-1 has only one possibility, so it equals ways at i-2
   //this handles numbers between 1-10 in two positions
   if (curChar == '0') {
    ways[i] = ((prevChar == '2' || prevChar == '1') ? ways[i - 2] : 0);
    ways[i - 1] = ways[i]; //i-1 should be same as i
   }
   //this is for numbers that has two possible ways to decode
   else if (curNum > 10 && curNum <= 26) ways[i] = ways[i - 2] + ways[i - 1];
   else //other situation has only 1 possible way to decode, so current ways of decoding is
   //equals to previous ways of decoding
   ways[i] = ways[i - 1];

  }
  return ways[s.length() - 1];
 }



 public static void main(String[] args) {
  //  System.out.println(numDecodings("99")    );
  //  System.out.println(numDecodings("27")    );
  //  System.out.println(numDecodings("301")    );
  //  System.out.println(numDecodings("08")    );
  System.out.println(numDecodings("110"));
  System.out.println(numDecodings("920"));
  System.out.println(numDecodings("20"));
 }

}

Test cases:

import static org.junit.Assert.*;

import org.junit.Test;


public class WaysDecodeTest {

 @Test
 public void testNumDecodings1() {
  int actual = Solution.numDecodings("99");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings2() {
  int actual = Solution.numDecodings("301");
  assertEquals(0, actual);
 }
 @Test
 public void testNumDecodings3() {
  int actual = Solution.numDecodings("27");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings4() {
  int actual = Solution.numDecodings("08");
  assertEquals(0, actual);
 }
 @Test
 public void testNumDecodings5() {
  int actual = Solution.numDecodings("12");
  assertEquals(2, actual);
 }
 
 @Test
 public void testNumDecodings6() {
  int actual = Solution.numDecodings("121");
  assertEquals(3, actual);
 }
 @Test
 public void testNumDecodings7() {
  int actual = Solution.numDecodings("2222");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings8() {
  int actual = Solution.numDecodings("22222");
  assertEquals(8, actual);
 }
 @Test
 public void testNumDecodings9() {
  int actual = Solution.numDecodings("22229");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings10() {
  int actual = Solution.numDecodings("222292");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings11() {
  int actual = Solution.numDecodings("2222920");
  assertEquals(5, actual);
 }
 @Test
 public void testNumDecodings12() {
  int actual = Solution.numDecodings("110");
  assertEquals(1, actual);
 }
 @Test
 public void testNumDecodings13() {
  int actual = Solution.numDecodings("20");
  assertEquals(1, actual);
 }
}