LeetCode - Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

public class Solution {
    public boolean isMatch(String s, String p) {
        if(p.length()==0) return s.length()==0;
     
        if(p.length()==1 || p.charAt(1)!='*'){
            if(s.length()<1 || (p.charAt(0)!='.' && p.charAt(0)!=s.charAt(0)))
                return false;
            return isMatch(s.substring(1),p.substring(1));
        }else{
            int i=-1;
            while(i<s.length() && (i<0 || p.charAt(0)=='.' || p.charAt(0)==s.charAt(i))){
                if(isMatch(s.substring(i+1),p.substring(2)))
                    return true;
                i++;
            }
            return false;
        }
    }
}


public class Solution {
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(s == null || p == null) return false;
        int m = s.length(), n = p.length();
        boolean[][] match = new boolean[m + 1][n + 1];
        match[0][0] = true;
        for(int i = 1; i <= m; i++){
            match[i][0] = false;
        }
        for(int j = 1; j <= n; j++){
            if(p.charAt(j - 1) == '*'){
                match[0][j] = match[0][j - 2];
            }else{
                match[0][j] = false;
            }
        }
      
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(p.charAt(j - 1) == '*'){
                    match[i][j] |= match[i][j - 2];
                    if(s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2)
== '.'){
                        match[i][j] |= match[i - 1][j];
                    }
                }else{
                    match[i][j] = ((s.charAt(i - 1) == p.charAt(j - 1) || p.
charAt(j - 1) == '.') && match[i - 1][j - 1]);
                }
            }
        }
      
        return match[m][n];
    }
}


public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] match = new boolean[m+1][n+1];
        match[0][0] = true;
        for(int i=1;i<=m;i++) {
            match[i][0] = false;
        }
        for(int j=1;j<=n;j++) {
            if(p.charAt(j-1)=='*') {
                match[0][j] = match[0][j-2];
            } else {
                match[0][j] = false;
            }
        }
     
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);
                if(pc=='*') {
                    match[i][j] = match[i][j-2] || match[i][j-1] || (match[i-1][j] && (sc==p.charAt(j-2) || p.charAt(j-2)=='.'));
                } else {
                    match[i][j] = match[i-1][j-1] && (sc==pc || pc=='.');
                }
            }
        }
        return match[m][n];
    }
}


class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length();
        int n = p.length();
        vector<vector<bool>> match(m + 1, vector<bool>(n + 1, false));
        match[0][0] = true;
        for(int i=1;i<=m;i++) {
            match[i][0] = false;
        }
        for(int j=1;j<=n;j++) {
            if(p[j-1]=='*') {
                match[0][j] = match[0][j-2];
            } else {
                match[0][j] = false;
            }
        }
       
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                if(p[j-1]=='*') {
                    match[i][j] = match[i][j-2] || match[i][j-1] || (match[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.'));
                } else {
                    match[i][j] = match[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.');
                }
            }
        }
        return match[m][n];
    }
};

LeetCode - 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

public class Solution {
     public boolean isMatch(String s, String p) {
        if (s == null || p == null)  return false;
 
        // calculate count for non-wildcard char
        int count = 0;
        for (Character c : p.toCharArray()) {
            if (c != '*')  ++count;
        }
        // the count should not be larger than that of s
        if (count > s.length())  return false;
 
        boolean[] matches = new boolean[s.length()+1];
        matches[0] = true;
        int pid = 0, firstMatch = 0;
        while (pid < p.length()) {
            // skip duplicate '*'
            if (pid > 0 && p.charAt(pid) == '*' && p.charAt(pid-1) == '*') {
                ++pid;
                continue;
            }
 
            // if '*', fill up the rest of row
            if (p.charAt(pid) == '*') {
                // fill up the rest of row with true, up to the first match in previous row
                for (int i = firstMatch+1; i <= s.length(); ++i)  matches[i] = true;
            } else {
                // fill up backwards:
                // - set to true if match current char and previous diagnal also match
                // - otherwise, set to false
                int match = -1;
                for (int i=s.length(); i>firstMatch; --i) {
                    matches[i] = (p.charAt(pid) == s.charAt(i-1) || p.charAt(pid) == '?')
                                && matches[i-1];
                    if (matches[i])  match = i;
                }
                if (match < 0)  return false;
                firstMatch = match;
            }
 
            ++pid;
        }
 
        return matches[s.length()];
    }
}

public class Solution {
     public boolean isMatch(String s, String p) {
        if (s == null || p == null)  return false;
 
        // calculate count for non-wildcard char
        int count = 0;
        for (Character c : p.toCharArray()) {
            if (c != '*')  ++count;
        }
        // the count should not be larger than that of s
        if (count > s.length())  return false;
        boolean[][] matches = new boolean[s.length()+1][p.length()+1];
        matches[0][0] = true;
        for(int i=1;i<=s.length();i++) {
            matches[i][0] = false;
        }
        for(int j=1;j<=p.length();j++) {
            matches[0][j] = matches[0][j-1] && p.charAt(j-1)=='*';
        }
        for(int i=1;i<=s.length();i++) {
            for(int j=1;j<=p.length();j++) {
                if(p.charAt(j-1)=='*') {
                    for(int k=i;k>=0;k--) {
                        if(matches[k][j-1]) {
                            matches[i][j] = true;
                            break;
                        }
                    }
                } else {
                    matches[i][j] = matches[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1)=='?');
                }
            }
        }
        return matches[s.length()][p.length()];
    }
}

===========

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int m = s.length();
        int n = p.length();
        boolean dp[][] = new boolean[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if (j == 0) {
                    dp[i][j] = false;
                } else if (i == 0) {
                    dp[i][j] = p.charAt(j - 1) == '*' && dp[i][j - 1];
                } else {
                    if (p.charAt(j - 1) != '*') {
                        dp[i][j] = (dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'));
                    } else {
                        if (dp[i - 1][j - 1]) {
                            for (int k = i - 1; k <= m; k++) {
                                dp[k][j] = true;
                            }
                        } else if (dp[i][j - 1]) {
                            dp[i][j] = true;
                        }
                    }
                }
            }
        }
        return dp[m][n];
    }
}

LeetCode - N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.



public class Solution {
    public int totalNQueens(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        assert(n>0);
        return solveNQueens(0,new int[n]);
    }
   
    public int solveNQueens(int n, int[] solves) {
        if(n==solves.length) {
            return 1;
        }
        int ret = 0;
        for(int i=0;i<solves.length;i++) {
            solves[n] = i;
            if(check(n, solves)) {
                ret += solveNQueens(n+1, solves);
            }
        }
        return ret;
    }

    private boolean check(int n, int[] solves) {
        for(int i=0;i<n;i++) {
            if(solves[i]==solves[n] || Math.abs(solves[i]-solves[n])==Math.abs(i-n)) {
                return false;
            }
        }
        return true;
    }
}

LeetCode - LRU Cache

 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.


public class LRUCache {
 
    HashMap<Integer, DoubleLinkedListNode> map;
    DoubleLinkedListNode head;
    DoubleLinkedListNode end;
    private int capacity;
    private int len;
 
    public LRUCache(int capacity) {
        this.map = new HashMap<Integer, DoubleLinkedListNode>();
        this.capacity = capacity;
        this.len = 0;
    }
 
    public int get(int key) {
        if(map.containsKey(key)) {
            DoubleLinkedListNode node = map.get(key);
            removeNode(node);
            setHead(node);
            return node.val;
        } else {
            return -1;
        }
    }

    private void removeNode(DoubleLinkedListNode node) {
        DoubleLinkedListNode pre = node.pre;
        DoubleLinkedListNode next = node.next;
        if(pre!=null) {
            pre.next = next;
        } else {
            head = next;
        }
        if(next!=null) {
            next.pre = pre;
        } else {
            end = pre;
        }
    }
 
    private void setHead(DoubleLinkedListNode node) {
        node.next = head;
        node.pre = null;
        if(head!=null) {
            head.pre = node;
        }
        head = node;
        if(end==null) {
            end = node;
        }
    }
 
    public void set(int key, int value) {
        if(map.containsKey(key)) {
            DoubleLinkedListNode oldNode = map.get(key);
oldNode.val = value;
removeNode(oldNode);
setHead(oldNode);
        } else {
            DoubleLinkedListNode newNode = new DoubleLinkedListNode(key, value);
            if(len<capacity) {
                setHead(newNode);
                map.put(newNode.key, newNode);
                len++;
            } else {
                map.remove(end.key);
                end = end.pre;
                if(end!=null) {
                    end.next = null;
                }
                setHead(newNode);
                map.put(newNode.key, newNode);
            }
        }
    }
 
    class DoubleLinkedListNode{
        int val;
        int key;
        DoubleLinkedListNode pre;
        DoubleLinkedListNode next;
     
        public DoubleLinkedListNode(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }
}


public class LRUCache {
   
    private int capacity;
    private HashMap<Integer, DoubleLinkNode> map;
   
    private DoubleLinkNode head;
    private DoubleLinkNode tail;
   
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<Integer, DoubleLinkNode>();
        head = new DoubleLinkNode(0, 0);
        tail = new DoubleLinkNode(0, 0);
        head.next = tail;
        tail.pre = head;
    }
   
    private void setToHead(DoubleLinkNode node) {
        // swap to head;
        if(node.pre!=head) {
            if(node.pre!=null)
                node.pre.next = node.next;
            if(node.next!=null)
                node.next.pre = node.pre;
            DoubleLinkNode tmpNext = head.next;
            tmpNext.pre = node;
            node.next = tmpNext;
            node.pre = head;
            head.next = node;
        }
    }
   
    public int get(int key) {
        if(map.containsKey(key)) {
            DoubleLinkNode node = map.get(key);
            setToHead(node);
            return node.val;
        } else {
            // error here
            return -1;
        }
    }
   
    public void set(int key, int value) {
        if(map.containsKey(key)) {
            DoubleLinkNode node = map.get(key);
            node.val = value;
            setToHead(node);
        } else {
            if(this.map.size()==this.capacity) {
                DoubleLinkNode remove = tail.pre;
                DoubleLinkNode tmp = remove.pre;
                tail.pre = tmp;
                tmp.next = tail;
                this.map.remove(remove.key);
            }
            DoubleLinkNode node = new DoubleLinkNode(key, value);
            this.map.put(key, node);
            setToHead(node);
        }
    }
   
    static class DoubleLinkNode {
        DoubleLinkNode pre;
        DoubleLinkNode next;
        int val;
        int key;
       
        public DoubleLinkNode(int key, int val) {
            this.val = val;
            this.key = key;
        }
    }
   
}

=========

public class LRUCache {
   
    public static class DoubleLinkedList {
        DoubleLinkedList prev;
        DoubleLinkedList next;
        private int key;
        private int val;
        public DoubleLinkedList(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
   
    HashMap<Integer, DoubleLinkedList> map;
    DoubleLinkedList head;
    DoubleLinkedList tail;
    int capacity;
   
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<Integer, DoubleLinkedList>();
    }
   
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        DoubleLinkedList node = map.get(key);
        moveToFront(node);
        return node.val;
    }
   
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            DoubleLinkedList node = map.get(key);
            node.val = value;
            moveToFront(node);
        } else {
            DoubleLinkedList node = new DoubleLinkedList(key, value);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                node.next = head;
                head.prev = node;
                head = node;
            }
            map.put(node.key, node);
            if (map.size() > capacity) {
                map.remove(tail.key);
                tail = tail.prev;
                tail.next = null;
            }
        }
    }
   
    private void moveToFront(DoubleLinkedList node) {
        if (node == head) {
            return;
        }
        if (node == tail) {
            tail = node.prev;
        }
        DoubleLinkedList oldPrev = node.prev;
        DoubleLinkedList oldNext = node.next;
        if (oldPrev != null) {
            oldPrev.next = oldNext;
        }
        if (oldNext != null) {
            oldNext.prev = oldPrev;
        }
        node.next = head;
        head.prev = node;
        head = node;
    }

}

LeetCode - Minimum Window Substring

 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S


public class Solution {
    public String minWindow(String S, String T) {
        if(S==null || T==null || S.length()<T.length()) {
            return "";
        }
        HashMap<Character, Integer> needFind = new HashMap<Character, Integer>();
HashMap<Character, Integer> alreadyFind = new HashMap<Character, Integer>();
for(int i=0;i<T.length();i++) {
   char c = T.charAt(i);
   alreadyFind.put(c, 0);
   if(needFind.containsKey(c)) {
       needFind.put(c, needFind.get(c) + 1);
   } else {
       needFind.put(c, 1);
   }
}
        int minStart = -1;
int minEnd = S.length();
int start = 0;
int len = 0;
for (int i = 0; i < S.length(); i++) {
   char c = S.charAt(i);
   if(needFind.containsKey(c)) {
       if(alreadyFind.get(c) < needFind.get(c)) {
           len++;
       }
       alreadyFind.put(c, alreadyFind.get(c) + 1);
       if(len==T.length()) {
           while(true) {
               if(!needFind.containsKey(S.charAt(start))) {
                   start++;
               } else {
                   if(alreadyFind.get(S.charAt(start))>needFind.get(S.charAt(start))) {
                       alreadyFind.put(S.charAt(start), alreadyFind.get(S.charAt(start))-1);
                       start++;
                   } else {
                       break;
                   }
               }
           }
           if(i-start<minEnd-minStart) {
               minStart = start;
               minEnd = i;
           }
       }
   }
}
if(minStart==-1) {
   return "";
} else {
   return S.substring(minStart, minEnd + 1);
}
    }
}

==========


public class Solution {
    public String minWindow(String s, String t) {
        if(s == null || t == null || t.length() > s.length()) {
            return "";
        }
        int[] remaining = new int[128];
        int required = t.length();
        int min = s.length() + 1, start = 0, left = 0;
        for (int i = 0; i < t.length(); i++){
            remaining[t.charAt(i)]++;
        }
        int i = 0;
        while (i <= s.length() && start < s.length()){
            if (required > 0){
                if (i == s.length()) {
                    break;
                }
                remaining[s.charAt(i)]--;
                if (remaining[s.charAt(i)] >= 0) {
                    required--;
                }
                i++;
            }
            if (required == 0) {
                if (i - start < min) {
                    min = i - start;
                    left = start;
                }
                remaining[s.charAt(start)]++;
                if (remaining[s.charAt(start)] > 0) {
                    required++;
                }
                start++;
            }
        }
        return min == s.length() + 1 ? "" : s.substring(left, left + min);
    }
}

LeetCode - 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"]
You should return the indices: [0,9].
(order does not matter).


public class Solution {
      public ArrayList<Integer> findSubstring(String S, String[] L) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(L==null || L.length==0) return null;
        int n = L.length, m = L[0].length(), l=S.length();
        ArrayList<Integer> res = new ArrayList<Integer>();
     
        Map<String,Integer> covered = new HashMap<String,Integer>();
        for(int j=0;j<n;j++){
            if(covered.containsKey(L[j])){
                covered.put(L[j],covered.get(L[j])+1);
            }else{
                covered.put(L[j], 1);
            }
        }
     
        int i=0;
        while(l-i>=n*m){
            Map<String, Integer> temp = new HashMap<String, Integer>(covered);
            for(int j=0;j<n;j++){
                String testStr = S.substring(i+j*m,i+(j+1)*m);
                if(temp.containsKey(testStr)){
                    if(temp.get(testStr)-1==0)
                        temp.remove(testStr);
                    else
                        temp.put(testStr,temp.get(testStr)-1);
                }else
                    break;
            }
            if(temp.size()==0) res.add(i);
            i++;
        }
        return res;  
    }
}

==============

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        int n = words.length;
        int len = words[0].length();
     
        for (int i = 0; i <= s.length() - n * len; i++) {
            HashMap<String, Integer> tmpMap = new HashMap<String, Integer>(map);
            int j = i;
            boolean qualified = true;
            while (tmpMap.size() != 0) {
                String nextSub = s.substring(j, j + len);
                Integer val = tmpMap.get(nextSub);
                if (val != null) {
                    if (val == 1) {
                        tmpMap.remove(nextSub);
                    } else {
                        tmpMap.put(nextSub, val - 1);
                    }
                    j += len;
                } else {
                    qualified = false;
                    break;
                }
            }
            if (qualified) res.add(i);
        }
        return res;
    }
}

========

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return res;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (String word : words) {
            if (map.containsKey(word)) {
                map.put(word, map.get(word) + 1);
            } else {
                map.put(word, 1);
            }
        }
        int len = words[0].length();
        for (int i = 0; i < len; i++) {
            HashMap<String, Integer> copy = new HashMap<>();
            int left = i;
            int right = i;
            while (true) {
                if (right - left != words.length * len) {
                    if (left + words.length * len > s.length()) break;
                    right += len;
                    if (right > s.length()) break;
                    String word = s.substring(right - len, right);
                    if (!map.containsKey(word)) {
                        copy.clear();
                        left = right;
                    } else {
                        while (copy.get(word) == map.get(word)) {
                            String word2 = s.substring(left, left + len);
                            copy.put(word2, copy.get(word2) - 1);
                            left += len;
                        }
                        if (!copy.containsKey(word)) {
                            copy.put(word, 1);
                        } else {
                            copy.put(word, copy.get(word) + 1);
                        }
                    }
                }
                if (words.length * len == right - left) {
                    res.add(left);
                    left += len;
                    String word = s.substring(left - len, left);
                    copy.put(word, copy.get(word) - 1);
                }
            }
        }
        return res;
    }
}

LeetCode - Recover Binary Search Tree

 Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

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; }

 * }

 */

public class Solution {

    

    TreeNode first;

    TreeNode second;

    TreeNode pre;

    int status;

    

    public void recoverTree(TreeNode root) {

        first = null;

        second = null;

        pre = null;

        status = 0;

        check(root);

        int tmp = first.val;

        first.val = second.val;

        second.val = tmp;

    }

    

    private void check(TreeNode node) {

        if(node==null || status==2) {

            return;

        }

        check(node.left);

        if(pre!=null && status==0 && pre.val>node.val) {

            status = 1;

            first = pre;

            second = node;

        } else if(pre!=null && status==1 && pre.val>node.val) {

            status = 2;

            second = node;

        }

        pre = node;

        check(node.right);

    }

}

=======

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    private TreeNode pre;
    private TreeNode first = null;
    private TreeNode second = null;
    public void recoverTree(TreeNode root) {
        visit(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
   
    private void visit(TreeNode node) {
        if (node == null) {
            return;
        }
        visit(node.left);
        if (pre != null) {
            if (pre.val > node.val) {
                if (first == null) {
                    first = pre;
                    second = node;
                } else {
                    second = node;
                   return;
                }
            }
        }
        pre = node;
        visit(node.right);
    }
}

LeetCode - Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.


public class Solution {
    public String getPermutation(int n, int k) {
        int num[] = new int[n];
        int count = 1;
        for(int i=0;i<n;i++) {
            num[i] = i+1;
            count *= num[i];
        }
        k -= 1;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            count /= (n-i);
            int sel = k/count;
            sb.append(num[sel]);
            k = k%count;
            for(int j=sel;j<num.length-1;j++) {
                num[j] = num[j+1];
            }
        }
        return sb.toString();
    }
}

============

public class Solution {
    public String getPermutation(int n, int k) {
        int count = 1;
        List<Integer> arr = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++) {
            count *= i;
            arr.add(i);
        }
        StringBuilder sb = new StringBuilder();
        k = k - 1;
        while (n > 0) {
            count /= n;
            int id = k /count;
            sb.append(arr.get(id));
            arr.remove(id);
            k = k % count;
            n--;
        }  
        return sb.toString();
    }
}

LeetCode - Scramble String

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.

public class Solution {

    public boolean isScramble(String s1, String s2) {

        if(s1==null || s2==null || s1.length()!=s2.length()) {

            return false;

        }

        char c1[] = s1.toCharArray();

        char c2[] = s2.toCharArray();

        Arrays.sort(c1);

        Arrays.sort(c2);

        String st1 = new String(c1);

        String st2 = new String(c2);

        if(!st1.equals(st2)) {

            return false;

        } else if(st1.length()<=2) {

            return true;

        }

        for(int i=0;i<s1.length()-1;i++) {

            if( (isScramble(s1.substring(0, i+1), s2.substring(0, i+1)) &&

                isScramble(s1.substring(i+1), s2.substring(i+1))) ||

                (isScramble(s1.substring(0, i+1), s2.substring(s1.length()-i-1)) &&

                isScramble(s1.substring(i+1), s2.substring(0, s1.length()-i-1))

                    )

                ) {

                    return true;

                }

        }

        return false;

    }

}

======

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        } else if (s1 == null || s2 == null) {
            return false;
        }
        if (s1.equals(s2)) return true;
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        if (!(new String(cs1)).equals(new String(cs2))) {
            return false;
        }
        for (int i = 1; i < s1.length(); i++) {
            if ((isScramble(s1.substring(0, i), s2.substring(0, i)) && isScramble(s1.substring(i), s2.substring(i))) ||
                (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) && isScramble(s1.substring(i), s2.substring(0, s2.length() - i)))
                ) return true;
        }
        return false;
    }
}

LeetCode - String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

public class Solution {
    public int atoi(String str) {
        if (str == null || str.length() < 1) {
   return 0;
        }
    str = str.trim();
    if(str.isEmpty()) {
       return 0;
    }
    boolean neg = false;
    if(str.charAt(0)=='-') {
       neg = true;
       str = str.substring(1);
    } else if(str.charAt(0)=='+') {
       str = str.substring(1);
    }
    double result = 0;
    int i = 0;
    while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
    result = result * 10 + (str.charAt(i) - '0');
    i++;
    }
    if (neg)
    result = -result;
    if (result > Integer.MAX_VALUE)
    return Integer.MAX_VALUE;
    if (result < Integer.MIN_VALUE)
    return Integer.MIN_VALUE;
    return (int) result;
    }
}

==========

public class Solution {
    public int myAtoi(String str) {
        if (str == null || str.length() == 0) return 0;
        int i = 0;
        int n = str.length();
        int sign = 1;
        while (i < n && Character.isWhitespace(str.charAt(i))) {
            i++;
        }
        if (str.charAt(i) == '-') {
            i++;
            sign = -1;
        } else if (str.charAt(i) == '+') {
            sign = 1;
            i++;
        }
        int total = 0;
        while (i < n) {
            int digit = str.charAt(i) - '0';
            if (digit < 0 || digit >= 10) {
                break;
            }
            if (Integer.MAX_VALUE / 10 < total || (Integer.MAX_VALUE / 10 == total && Integer.MAX_VALUE % 10 < digit)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            total = total * 10 + digit;
            i++;
        }
        return total * sign;
    }
}

=============

public class Solution {
    public int myAtoi(String str) {
        if (str == null) {
            return 0;
        }
        int res = 0;
        int sign = 1;
        str = str.trim();
        int i = 0;
        int n = str.length();
        if (i < n && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
            if (str.charAt(i) == '-') sign = -1;
            i++;
        }
        while (i < n && Character.isDigit(str.charAt(i))) {
            int digit = str.charAt(i) - '0';
            if (Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res && Integer.MAX_VALUE % 10 < digit)) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res *= 10;
            res += digit;
            i++;
        }
        return res * sign;
    }
}

LeetCode - Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.


public class Solution {
    public boolean search(int[] A, int target) {
        if(A==null || A.length==0) {
            return false;
        }
        int start = 0;
        int end = A.length - 1;
        while(start<=end) {
            int mid = (start+end)/2;
            if(A[mid]==target) {
                return true;
            }
            // left is sorted
            if(A[start]<A[mid]) {
                if(target>=A[start] && target<A[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else if(A[start]>A[mid]) {
                if(target>A[mid] && target<=A[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                start++;
            }
        }
        return false;
    }
}

=========

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int s = 0;
        int e = nums.length - 1;
        while (s <= e) {
            int m = (s + e) / 2;
            if (nums[m] == target) {
                return true;
            } else {
                // left is sorted
                boolean leftSorted = true;
                for (int i = s; i < m; i++) {
                    if (nums[i] > nums[i+1]) {
                        leftSorted = false;
                        break;
                    }
                }
                if (leftSorted) {
                    if (target >= nums[s] && target <= nums[m]) {
                        e = m - 1;
                    } else {
                        s = m + 1;
                    }
                } else {
                    if (target >= nums[m] && target <= nums[e]) {
                        s = m + 1;
                    } else {
                        e = m - 1;
                    }
                }
            }
        }
        return false;
    }
}

LeetCode - Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.


public class Solution {
    public int search(int[] A, int target) {
        if(A==null || A.length==0) {
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while(start<=end) {
            int mid = (start+end)/2;
            if(A[mid]==target) {
                return mid;
            } else if(A[mid]<target) {
                if(A[start]<A[end] || A[start]<A[mid] || target<=A[end]) {
                    start = mid + 1;
                } else {
                    end = mid -1;
                }
            } else {
                if(A[start]<A[end] || A[mid]<A[end] || target>=A[start]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
        }
        return -1;
    }
}


public class Solution {
    public int search(int[] A, int target) {
        if(A==null || A.length==0) {
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while(start<=end) {
            int mid = (start+end)/2;
            if(A[mid]==target) {
                return mid;
            }
            // left is sorted
            if(A[start]<=A[mid]) {
                if(target<A[mid] && target>=A[start]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if(target>A[mid] && target<=A[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
}