Text Justification (LeetCode String)

Question: 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.  "
]

Idea: Brute force. Accumulate the length of the words, if the total length is above L or reach the end of the file, add spaces. There are two cases:
1) one word a line or the end of the file, left alignment (append one space for each word, then add empty space to L length.
2) the others: calculate the average number of spaces per word, first a few words need average+1, the other words need the average number, the last word does not append anything.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public List<String> fullJustify(String[] words, int L) {  
     List<String> result=new ArrayList<String>();  
     int curLength=0;  
     int lastI=0;  
     int wordCount=words.length;  
     for(int i=0;i<=wordCount;i++)  
     {  
       if(i==wordCount||curLength+words[i].length()+i-lastI>L)  
       {  
         StringBuilder builder=new StringBuilder();  
         int spaceCount=L-curLength;  
         int spaceSlot=i-lastI-1;  
         if(spaceSlot==0||i==wordCount)  
         {  
           for(int j=lastI;j<i;j++)  
           {  
             builder.append(words[j]);  
             if(j!=i-1)  
               appendSpace(builder,1);  
           }  
           appendSpace(builder,L-builder.length());  
         }  
         else  
         {  
           int spaceEach=spaceCount/spaceSlot;  
           int spaceExtra=spaceCount%spaceSlot;  
           for(int j=lastI;j<i;j++)  
           {  
             builder.append(words[j]);  
             if(j!=i-1)  
             {  
               appendSpace(builder,spaceEach+(j-lastI<spaceExtra?1:0));  
             }  
           }  
         }  
         result.add(builder.toString());  
         lastI=i;  
         curLength=0;  
       }  
       if(i<wordCount)  
         curLength+=words[i].length();  
     }  
     return result;  
   }  
   public void appendSpace(StringBuilder builder,int n)  
   {  
     for(int i=0;i<n;i++)  
       builder.append(' ');  
   }  
 }  

Scramble String (LeetCode String)

Question: Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Idea: Brute force. Try all possible ways to split s1 and s2 each to two substrings, then recursively test whether any way of split is a scramble, then return true.

Time: 

 public class Solution {  
   public boolean isScramble(String s1, String s2) {  
     HashMap<Character,Integer> counter=new HashMap<Character,Integer>();  
     for(char c:s1.toCharArray())  
     {  
       if(counter.containsKey(c))  
         counter.put(c,counter.get(c)+1);  
       else  
         counter.put(c,1);  
     }  
     for(char c:s2.toCharArray())  
     {  
       if(counter.containsKey(c))  
         counter.put(c,counter.get(c)-1);  
       else  
         return false;  
     }  
     for(Character key:counter.keySet())  
     {  
       if(counter.get(key)!=0)  
         return false;  
     }  
     if(s1.length()==1)  
       return true;  
     for(int i=1;i<s1.length();i++)  
     {  
       String sub11=s1.substring(0,i);  
       String sub12=s1.substring(i);  
       String sub21=s2.substring(0,i);  
       String sub22=s2.substring(i);  
       String sub31=s2.substring(0,s2.length()-i);  
       String sub32=s2.substring(s2.length()-i);  
       if(isScramble(sub11,sub21)&&isScramble(sub12,sub22))  
         return true;  
       if(isScramble(sub11,sub32)&&isScramble(sub12,sub31))  
         return true;  
     }  
     return false;  
   }  
 }  

Restore IP Addresses (LeetCode String)

Question: Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Idea: Brute force. Use three pointers to split the string into four substrings, then check whether all the four substrings are valid. If yes, add to the result, otherwise continue.

Time: O(n^3) Space: O(n)

Code:

 public class Solution {  
   public List<String> restoreIpAddresses(String s) {  
     List<String> result=new ArrayList<String>();  
     if(s.length()<4)  
       return result;  
     for(int i=1;i<4&&i<s.length()-2;i++)  
     {  
       for(int j=i+1;j<i+4&&j<s.length()-1;j++)  
       {  
         for(int k=j+1;k<j+4&&k<s.length();k++)  
         {  
           String sub1=s.substring(0,i);  
           String sub2=s.substring(i,j);  
           String sub3=s.substring(j,k);  
           String sub4=s.substring(k);  
           if(isValid(sub1)&&isValid(sub2)&&isValid(sub3)&&isValid(sub4))  
             result.add(sub1+"."+sub2+"."+sub3+"."+sub4);  
         }  
       }  
     }  
     return result;  
   }  
   public boolean isValid(String s)  
   {  
     if(s.length()==0||s.length()>3||(s.charAt(0)=='0'&&s.length()>1)||Integer.parseInt(s)>255)  
       return false;  
     return true;  
   }  
 }  

Add Two Numbers (LeetCode Linked List)

Question: You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Idea: Brute force. Keep adding if l1 or l2 is not empty or the carry is not 0. Keep a pointer pointing consistently to the head of the intended results, otherwise it is impossible to find the head of the result when the result is going to be returned : (

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
     ListNode dummy=new ListNode(-1);  
     ListNode cur=dummy;  
     int carry=0;  
     while(l1!=null||l2!=null||carry!=0)  
     {  
       int valOne=0;  
       int valTwo=0;  
       if(l1!=null)  
       {  
         valOne=l1.val;  
         l1=l1.next;  
       }  
       if(l2!=null)  
       {  
         valTwo=l2.val;  
         l2=l2.next;  
       }  
       int sum=valOne+valTwo+carry;  
       carry=sum/10;  
       sum=sum%10;  
       cur.next=new ListNode(sum);  
       cur=cur.next;  
     }  
     return dummy.next;  
   }  
 }  

Word Search (LeetCode Array)

Question: Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Idea: Depth-first search with backtracking. For each block, start to match the string one character by one character. Whenever a character board[i][j] is matched, mark it as board[i][j]='#' (representing it has been used) then go forward to board[i+1][j], board[i-1][j], board[i][j+1] and board[i][j-1]. If board[i][j] is out of boundary or board[next] does not match with string[next], return false. When all the characters of the string is matched, return true. When we roll back to the point board[i][j], do not forget to set it back to the original character, otherwise when we initial another search from the next point, e.g. board[i][j-1], the path can not go left, since it is '#'.

Time: O(n^4) Space: O(n^2)

Code:

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     if(board.length==0||board[0].length==0||board.length*board[0].length<word.length())  
       return false;  
     boolean result=false;  
     for(int i=0;i<board.length;i++)  
     {  
       for(int j=0;j<board[0].length;j++)  
       {  
         result=result||dfs(board,word,i,j,0);      
       }  
     }  
     return result;  
   }  
   public boolean dfs(char[][] board,String word,int startX,int startY,int curC)  
   {  
     if(curC==word.length())  
       return true;  
     if(startX>=board.length||startX<0)  
       return false;  
     if(startY>=board[0].length||startY<0)  
       return false;  
     if(board[startX][startY]!=word.charAt(curC))  
       return false;  
     char tmp=board[startX][startY];  
     board[startX][startY]='#';  
     boolean result=dfs(board,word,startX+1,startY,curC+1)||  
     dfs(board,word,startX-1,startY,curC+1)||  
     dfs(board,word,startX,startY+1,curC+1)||  
     dfs(board,word,startX,startY-1,curC+1);  
     board[startX][startY]=tmp;  
     return result;  
   }  
 }  

Subsets II (LeetCode Array)

Question: Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Idea: Brute force. The only thing is to skip the adjacent duplicates.

Time: O(2^n) Space: O(1)

Iterative Code:

 public class Solution {  
   public List<List<Integer>> subsetsWithDup(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     result.add(new ArrayList<Integer>());  
     Arrays.sort(num);  
     int preSize=0;  
     for(int i=0;i<num.length;i++)  
     {  
       int curSize=result.size();  
       for(int j=0;j<curSize;j++)  
       {  
         if(i==0||num[i]!=num[i-1]||j>=preSize)  
         {  
           List<Integer> oneRow=new ArrayList<Integer>(result.get(j));  
           oneRow.add(num[i]);  
           result.add(oneRow);  
         }  
       }  
       preSize=curSize;  
     }  
     return result;  
   }  
 }  

Recursive Code:

 public class Solution {  
   public List<List<Integer>> subsetsWithDup(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     Arrays.sort(num);  
     dfs(result,path,num,0);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result,List<Integer> path,int[] num,int start)  
   {  
     result.add(new ArrayList<Integer>(path));  
     for(int i=start;i<num.length;i++)  
     {  
       if(i!=start&&num[i]==num[i-1])  
         continue;  
       path.add(num[i]);  
       dfs(result,path,num,i+1);  
       path.remove(path.size()-1);  
     }  
   }  
 }  

Subsets (LeetCode Array)

Question: Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Idea: Brute force. There are many ways to list all the combinations. I only write the recursion method and the iterative method as following.

Time: O(2^n) Space: O(n) for recursive, O(1) for iterative.

Recursive Code:

 public class Solution {  
   public List<List<Integer>> subsets(int[] S) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(S==null||S.length==0)  
       return result;  
     Arrays.sort(S);  
     List<Integer> path=new ArrayList<Integer>();  
     dfs(result,path,S,0);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result, List<Integer> path, int[] S, int start)  
   {  
     result.add(new ArrayList<Integer>(path));  
     for(int i=start;i<S.length;i++)  
     {  
       path.add(S[i]);  
       dfs(result,path,S,i+1);  
       path.remove(path.size()-1);  
     }  
   }  
 }  

Iterative Code:

 public class Solution {  
   public List<List<Integer>> subsets(int[] S) {  
     Arrays.sort(S);  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     result.add(new ArrayList<Integer>());  
     for(int i=0;i<S.length;i++)  
     {  
       int curSize=result.size();  
       for(int j=0;j<curSize;j++)  
       {  
         List<Integer> cur=new ArrayList<Integer>(result.get(j));  
         cur.add(S[i]);  
         result.add(cur);  
       }  
     }  
     return result;  
   }  
 }  

Plus One (LeetCode Array)

Question: Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.

Idea: From the end of the input array, keep adding 1 until the carry becomes zero. There is a special case that if all the digits are 9, e.g. 999999. The carry will still be 1 after adding the most significant digit. Then we need to initial another array with the first digit as 1 and all the rest digits as 0.

Time: O(n) Space: O(n) (worst case when all digits are 9, we need a new array to store the result)

Code:

 public class Solution {  
   public int[] plusOne(int[] digits) {  
     for(int i=digits.length-1;i>=0;i--)  
     {  
       digits[i]=digits[i]+1;  
       if(digits[i]>=10)  
         digits[i]-=10;  
       else  
         return digits;  
     }  
     int[] result=new int[digits.length+1];  
     result[0]=1;  
     return result;  
   }  
 }  

Pascal's Triangle (LeetCode Array)

Question: Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Idea: Brute force. Generate the triangle row by row.

Time: O(n^n) Space: O(n^n)

Code:

 public class Solution {  
   public List<List<Integer>> generate(int numRows) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     if(numRows<1)  
       return result;  
     ArrayList<Integer> lastRow=new ArrayList<Integer>();  
     lastRow.add(1);  
     for(int i=1;i<=numRows;i++)  
     {  
       result.add(lastRow);  
       ArrayList<Integer> newRow=new ArrayList<Integer>();  
       newRow.add(1);  
       for(int j=0;j<lastRow.size()-1;j++)  
         newRow.add(lastRow.get(j)+lastRow.get(j+1));  
       newRow.add(1);  
       lastRow=newRow;  
     }  
     return result;  
   }  
 }