LeetCode: Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Solution:

The key is not to use recursion，but iteration based on DP. This would save much computation. 

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        vector<bool> checked(s.length()+1, false);
        checked[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (checked[j] && dict.find(s.substr(j,i-j)) != dict.end()) {
                    checked[i] = true;
                    break;
                }
            }
        }
        return checked[s.length()];
    }
};

LeetCode: Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int i = 0, j = 0, sum = 0;
        while (i < gas.size() && j != i + gas.size()) {
            sum += gas[j%gas.size()] - cost[j%gas.size()];
            while (sum < 0 && i <= j && i < gas.size()) {
                sum -= gas[i] - cost[i];
                ++i;
            }
            ++j;
        } 
        if (i == gas.size()) {
            return -1;
        } else {
            return i;
        }
    }
};

LeetCode: Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.


What is the minimum candies you must give?

class Solution {
public:
    int candy(vector<int> &ratings) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<int> candies(ratings.size());
        for (int i = 0; i < ratings.size(); ++i) {
            if (i > 0 && ratings[i] > ratings[i-1]) {
                candies[i] = candies[i-1]+1;
            }
        }
        int res = ratings.size() > 0 ?
            ratings.size() + candies[ratings.size()-1] : ratings.size(); 
        for (int i = ratings.size()-2; i>=0; --i) {
            if (ratings[i] > ratings[i+1]) {
                candies[i] = candies[i] < candies[i+1]+1 ? 
                    candies[i+1]+1 : candies[i];
            }
            res += candies[i];
        }
        return res;
    }
};

LeetCode: Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.



Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


Idea: if we look all the last bit of the numbers (assuming all are 32-bit) in the array, there must be 3k+1 or 3k `1's in total depending whether the single number's last bit is one or zero. This observation holds for all the rest 31 bits as well. Hence, if we sum all the numbers only at certain bit and mod by 3, we can get the corresponding bit the single number. Do this for all 32-bit, we can get all bits of that number. This generalizes the solution of LeetCode: Single Number I, where xor all the numbers is essentially trying to add all bits and then mod by 2...




Solution in C++:

class Solution {
public:
    int singleNumber(int A[], int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int single_number = 0;
        for (int i = 0; i < 32; ++i) {// assume dealing with int32.
            int bit = 0;
            for (int j = 0; j < n; ++j) {
                bit = (bit + ((A[j] >> i) & 1)) % 3;
            }
            single_number += (bit << i);
        }
        return single_number;
    }
};

Photo: Time Scare

LeetCode: Multiply Strings

Multiply StringsMar 12 '12


Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

public class Solution {
    public String multiply(String num1, String num2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        int[] num = new int[num1.length()+num2.length()];
        for(int i=0;i<num1.length();i++){
            int carry = 0;
            int a = num1.charAt(num1.length()-1-i)-'0';
            for(int j=0;j<num2.length();j++){
                int  b = num2.charAt(num2.length()-1-j)-'0';
                num[i+j]+=carry+a*b;
                carry=num[i+j]/10;
                num[i+j]%=10;
            }
            num[i+num2.length()]+=carry;
        }
        int i=num.length-1;
        while(i>0 && num[i]==0) i--;
        
        StringBuilder temp = new StringBuilder("");
        while(i>=0)
            temp.append((char)('0'+num[i--]));
        
        return temp.toString();
    }
}

LeetCode:Unique Binary Search Trees II

Unique Binary Search Trees IIAug 27 '12

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; left = null; right = null; }
 * }
 */
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        return generateTrees(1,n);
    }
    
    public ArrayList<TreeNode> generateTrees(int a, int b){
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        
        if(a>b){
            res.add(null);   
        }else if(a==b){
            res.add(new TreeNode(a));
        }else if(a<b){
            for(int i=a;i<=b;i++){
                ArrayList<TreeNode> temp1 = generateTrees(a,i-1);
                ArrayList<TreeNode> temp2 = generateTrees(i+1,b);
                
                for(TreeNode n:temp1){
                    for(TreeNode m:temp2){
                        TreeNode temp= new TreeNode(i);
                        temp.left=n;
                        temp.right=m;
                        res.add(temp);
                    }
                }

            }
        } 
        return res;
    }
}

LeetCode:Word Search

Word SearchApr 18 '12



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.
DFS and use a boolean array to keep track if one coordinate was visited or not. 

public class Solution {
    public boolean exist(char[][] board, String word) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        if(word==null || word.length()==0) return true;
        
        int m = board.length,
            n = board[0].length;
        char[] letters = word.toCharArray();
        boolean[][] tried = new boolean[m][n];
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==letters[0]){
                    tried = new boolean[m][n];
                    Stack<Integer[]> toVisit = new Stack<Integer[]>();
                    Integer[] temp = new Integer[2];
                    temp[0]=i*n+j; 
                    temp[1]=0;
                    toVisit.push(temp);
                    
                    
                    while(!toVisit.isEmpty()){
                        Integer[] cur = toVisit.pop();
                        if(!tried[cur[0]/n][cur[0]%n] && board[cur[0]/n][cur[0]%n]==letters[cur[1]]){
                            if(cur[1]==word.length()-1) return true;
                            tried[cur[0]/n][cur[0]%n]=true;
                            
                            for(int ii=-1;ii<=1;ii++){
                                for(int jj=-1;jj<=1;jj++){
                                    if((ii==0||jj==0) && cur[0]/n+ii>=0 && cur[0]/n+ii<m && cur[0]%n+jj>=0 && cur[0]%n+jj<n && !tried[cur[0]/n+ii][cur[0]%n+jj]){
                                        Integer[] temp1 = new Integer[2];
                                        temp1[0]=cur[0]/n*n+ii*n+cur[0]%n+jj;
                                        temp1[1]=cur[1]+1;
                                        toVisit.push(temp1);
                                    }
                                }
                            }
                            
                        }
                    }                 
                }
            }
        }
        return false;
        
    }
}

LeetCode: Wildcard Matching

Wildcard Matching


Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Idea: The pattern string can be something+'*'+something+'*'+something+`*'+...+'*'+something+'*'+something. We first deal with the matching of the head and tail (before the first `*` and after the last `*'). Then the pattern string left is '*'+something+'*'+something+`*'+...+'*'+something+'*', for which, we use greedy algorithm to find the first appearance of each something. So the total time required is O(m*n).

public class Solution {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
        assert(s!=null && p!=null);    
        if(p.length()==0) return s.length()==0;
        
        //deal with head
        int i=0;
        while(i<p.length() && i<s.length() && p.charAt(i)!='*'){
            if(p.charAt(i)!=s.charAt(i) && p.charAt(i)!='?')
                return false;
            i++;
        }
        if(i==s.length()){
              while(i<p.length())
                if(p.charAt(i++)!='*') return false;
            return true;
        }
        else if(i==p.length()) 
            return false;
        else{
           s=s.substring(i);
           p=p.substring(i);
        }
        
        //deal with tail 
        i=p.length()-1;
        int j = s.length()-1;
        while(i>=0 && j>=0 && p.charAt(i)!='*'){
            if(p.charAt(i)!=s.charAt(j) && p.charAt(i)!='?')
                return false;
            i--;
            j--;
        }
        if(j<0){
            while(i>=0)
                if(p.charAt(i--)!='*') return false;
            return true;
        }
        else if(i<0)
            return false;
        else{
            s=s.substring(0,j+1);
            p=p.substring(0,i+1);
        }
        
        String[] pattern = p.split("[*]");
        for(String temp:pattern){
            if(temp.length()>0){
                int index = getFirstIndex(s,temp);
                if(index<0) 
                    return false;
                else
                    s=s.substring(index+temp.length());
            }    
        }   
        return true;
    }
    
    
    public int getFirstIndex(String s, String p){
        if(s.length()<p.length()) return -1;
        int i=0;
        while(i<=s.length()-p.length()){
            while(i<s.length() && p.charAt(0)!='?' && p.charAt(0)!=s.charAt(i))
                i++;
            if(s.length()-i<p.length()) return -1;
            
            int j=i;
            while(j-i<p.length() && (p.charAt(j-i)=='?'||p.charAt(j-i)==s.charAt(j)))
                j++;
            if(j-i==p.length()) return i;
            i++;
        }
        return -1;
    }
}