Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces' ' when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Corner Cases:

• A line other than the last line might contain only one word. What should you do in this case?
  In this case, that line should be left-justified.

The solution to this question is quite straightforward. But you must write it down very carefully!

Java: TextJustification

public class Solution {
   public ArrayList<String> fullJustify(String[] words, int L) {
       ArrayList<String> result=new ArrayList<String>();
       int i=0;      
       while(i<words.length)
       {
           //store all words of a line together          
           ArrayList<String> line=new ArrayList<String>();          
           int len=0;
         
           while(len+words[i].length()<=L)
           {              
               line.add(words[i]);
               len+=words[i].length()+1;              
               i++;
               if(i==words.length)
                   break;
           }
       
           StringBuffer sb=new StringBuffer();
         
           //case1: only one word in a line
           if(line.size()==1)
           {
               String word1=line.get(0);
               sb.append(word1);
               for(int j=0;j<L-word1.length();j++)
               {
                   sb.append(" ");
               }
               result.add(sb.toString());
           }
         
           //case2: last line
           else if(i==words.length)
           {
               int totalLength=0;
               for(int j=0;j<line.size()-1;j++)
               {
                   String str=line.get(j);
                 
                   sb.append(str);
                   sb.append(" ");
                   totalLength+=str.length()+1;
               }
               String lastWord=line.get(line.size()-1);
               sb.append(lastWord);
               totalLength+=lastWord.length();              
               for(int j=0;j<L-totalLength;j++)
               {
                   sb.append(" ");
               }
               result.add(sb.toString());
           }
       
           //case 3: justify from two ends
           else
           {
               int totalLength=line.get(0).length();
               int lineSize=line.size();
               for(int j=1;j<lineSize;j++)
               {
                   totalLength+=line.get(j).length();
               }
               int numSpace=L-totalLength;              
               int avgSpace=numSpace/(lineSize-1);
               int remainSpace=numSpace%(lineSize-1);
             
               for(int j=0;j<lineSize-1;j++)
               {
                   sb.append(line.get(j));
                 
                   //distribute spaces evenly
                   for(int k=0;k<avgSpace;k++)
                   {
                       sb.append(" ");
                   }
                 
                   //distribute remaining spaces
                   if(remainSpace>0)
                   {
                       sb.append(" ");
                       remainSpace--;
                   }
               }
               String lastWord=line.get(lineSize-1);
               sb.append(lastWord);
               result.add(sb.toString());
           }                      
       }
   
       return result;
   }
}

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 n^th sequence.

Note: The sequence of integers will be represented as a string.

This question is a typical DP problem. The nth sequence can be calculated from the (n-1)th sequence. Therefore, we just store the result of each step.

Java: CountAndSay

public String countAndSay(int n) {
   String []sequence=new String[n];
   sequence[0]="1";
 
   for(int i=1;i<n;i++)
   {
       char[] str=sequence[i-1].toCharArray();
       StringBuffer sb=new StringBuffer();
       int start_value=str[0]-'0';
       int j=1;
       int counter=1;
       while(j<str.length)
       {
           if(str[j]-'0'==start_value)
           {
               counter++;
           }
           else
           {
               sb.append(counter);
               sb.append(start_value);
               start_value=str[j]-'0';
               counter=1;
           }
           j++;
       }
       sb.append(counter);
       sb.append(start_value);
       sequence[i]=sb.toString();
   }
 
   return sequence[n-1];
}

Decode Ways

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.

In this problem, you should consider many cases, and some of them are tricky.

1. If there is one digit, then it's obvious. If the digit is not equal to 0, we have only one way to decode. If the digit is 0, we have no ways to decode.

2. If the number has two digits. You should consider
10: 1 way,
11-19 : 2 ways,
20: 1 way,
21-26: 2 ways,
27-29: 1 way
30,40,50,...,90: 0 way
31-39, 41-49,...,91-99: 1 way

3. If the number has len>=3 digits or more, the number is
1) the first digit starts with 0,
   decodeWays=0;
2) the first two digits are from 11 to 19 or 22 to 26
decodeWays(x)=decodeWays(1 digit after x)+  decodeWays(2 digits after x)
3) the first two digits are others
decodeWays(x)=decodeWays(1 digit after x)

After considering these trivial cases, you can start coding. But, keep in mind that the recursion call is very expensive. I tried the first time using recursion, then the time limit exceeded.

Then I use DP to store the intermediate decodeWays. Keeping these values, recursion is avoided.

Java: DecodeWays

public int numDecodings(String s) {
   if(s.length()<1)
       return 0;
 
   char[]str=s.toCharArray();
 
   int[]decodeWays=new int[str.length];
   int last=str.length-1;
   if(str[last]-'0'==0)
       decodeWays[last]=0;
   else
       decodeWays[last]=1;
   if(last>=1)
   {
       if(str[last-1]-'0'>2)
       {
           if(str[last]-'0'==0)
               decodeWays[last-1]=0;
           else
               decodeWays[last-1]=1;
       }
       else if(str[last-1]-'0'==2)
       {
           if(str[last]-'0'>6)
               decodeWays[last-1]=1;
           else if(str[last]-'0'==0)
               decodeWays[last-1]=1;
           else
               decodeWays[last-1]=2;
       }
       else if(str[last-1]-'0'==1)
       {
           if(str[last]-'0'==0)
               decodeWays[last-1]=1;
           else
               decodeWays[last-1]=2;
       }
       else
       {
           decodeWays[last-1]=0;
       }
   }
 
   if(last>=2)
   {
       for(int i=last-2;i>=0;i--)
       {
           if(str[i]-'0'==0)
               decodeWays[i]=0;
           else
           {
               int ways=0;
               if(str[i]-'0'<2||(str[i]-'0'==2 && str[i+1]-'0'<=6))
                   ways=1;
               decodeWays[i]=decodeWays[i+1]+ways*decodeWays[i+2];
           }
       }
   }
 
   return decodeWays[0];      
 
}

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]




Java: Substring with Concatenation of All Words

public ArrayList<Integer> findSubstring(String S, String[] L) {
   ArrayList<Integer> result=new ArrayList<Integer>();
   Hashtable<String,Integer>ht=new Hashtable<String,Integer>();
   for(int i=0;i<L.length;i++)
   {
       if(!ht.containsKey(L[i]))
       {
           ht.put(L[i],1);
       }
   }
   int len=L[0].length();              
   int totalLen=L.length*len;
   int start=0;
   while(start+totalLen<=S.length())
   {
       String tempStr=S.substring(start,start+totalLen);
       String starter=tempStr.substring(0,len);
       if(!ht.containsKey(starter))
       {
           start++;
           continue;
       }
                 
       String[] strs=new String[L.length];  
       ArrayList<String>show=new ArrayList<String>();
       for(int i=0;i+len<=totalLen;i=i+len)
       {
           strs[i/len]=tempStr.substring(i,i+len);
           show.add(strs[i/len]);
       }
       for(int j=0;j<L.length;j++)
       {
           if(show.contains(L[j]))
               show.remove(L[j]);
           else
               break;
       }
       if(show.isEmpty())
       {
           result.add(start);
           start=start+len;
       }
       else
       {              
           start++;            
       }                  
   }
 
   return result;
}

Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

This question looks very much similar to the merge step of external sorting.

http://en.wikipedia.org/wiki/External_sorting 

The time complexity of this merge takes O(nk) in our process because each time we take O(k) to find the minimum of each pass, and we have n passes. However, if we use a data structure of heap or tournament tree when finding the min element, the complexity can be reduced to O(nlogk).

public class ListNode {
   int val;
   ListNode next;
   ListNode(int x) {
       val = x;
       next = null;
   }
}

Java: MergeKSortedLists

public ListNode mergeKLists(ArrayList<ListNode> lists) {
   if(lists.isEmpty())
       return null;
   ArrayList<ListNode> nodes=new ArrayList<ListNode>();
   for(int i=0;i<lists.size();i++)
   {
       if(lists.get(i)!=null)
           nodes.add(lists.get(i));
   }
 
   if(nodes.isEmpty())
       return null;          
   ListNode min;      
   ListNode head=null;
   ListNode curr=head;
 
   while(!nodes.isEmpty())
   {          
       min=nodes.get(0);
       for(int i=0;i<nodes.size();i++)
       {
           if( nodes.get(i).val<=min.val)
           {                                      
               min=nodes.get(i);
           }
       }
     
       if(head==null)
       {
           head=min;
           curr=head;
       }          
     
       else
       {          
           curr.next=min;
           curr=curr.next;
       }
     
       nodes.remove(min);
       if(min.next!=null)
           nodes.add(min.next);          
   }
 
   return head;
}

Same Binary Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

C++: 

bool isSameTree(TreeNode *p, TreeNode *q) {
   if(!p)
   {
       if(!q)
       {
           return true;
       }
       else
       {
           return false;
       }
   }
   if(p && !q)
   {
       return false;
   }
   if(p->val==q->val)
   {
       return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
   }
   else
   {
       return false;
   }
     
}

RecoverBST

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Idea:

This question is not hard to understand, but you must think about it carefully. How can you detect the two dis-ordered elements?

The most straightforward idea is to do an in-order traverse from the beginning to the end. When you detect that a node is larger then the next one, then that node is the first disordered element.

But, how can you detect the second disordered elements? Maybe you can do another in-order traverse from the back to the front, and detect the first one that is larger then its next one. This is not necessary.

When two nodes interchange in a BST, it must be that a larger one comes first, and the smaller one comes later, and that smaller one must be the minimum of the remaining nodes! Then you find it. In the end, you just modify the value of the two nodes.

Java: BinaryTree

public class TreeNode {
   int val;
   TreeNode left;
   TreeNode right;
   TreeNode(int x) { val = x; }
}

Java: RecoverBST

01 public void recoverTree(TreeNode root) {
02      Stack<TreeNode>st=new Stack<TreeNode>();
03      TreeNode first=null;
04      TreeNode second=null;
05      int min=root.val;
06      if(root!=null)
07      {
08          st.push(root);
09          while(root.left!=null)
10          {
11              root=root.left;
12              st.push(root);
13          }          
14      }
15     
16      while(!st.empty())
17      {
18          TreeNode top=st.pop();          
19          TreeNode curr=top;
20          TreeNode next=curr;          
21          if(curr.right!=null)
22          {
23              st.push(curr.right);
24              curr=curr.right;
25              while(curr.left!=null)
26              {
27                  st.push(curr.left);
28                  curr=curr.left;                  
29              }
30          }
31         
32          if(!st.empty())
33          {
34              next=st.peek();
35          }
36         
37          if(top.val>next.val && first==null)
38          {
39              first=top;
40              second=next;
41              min=next.val;
42          }              
43         
44          if(first!=null && top.val<=min)
45          {
46              min=top.val;
47              second=top;
48          }
49      }
50     
51      int temp=first.val;
52      first.val=second.val;
53      second.val=temp;
54  }