LeetCode - Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

click to show clarification.

public class Solution {

    public String reverseWords(String s) {

        String tks[] = s.split("\\s+");

        StringBuilder sb = new StringBuilder();

        for(int k=tks.length-1;k>=0;k--) {

            sb.append(tks[k]).append(" ");

        }

        return sb.toString().trim();

    }

}

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

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() < 1) {
            return s;
        }
        char[] cs = s.toCharArray();
        swap(cs, 0, cs.length - 1);
        int i = 0;
        while (i < cs.length) {
            while (i < cs.length && Character.isWhitespace(cs[i])) i++;
            int start = i;
            while (i < cs.length && !Character.isWhitespace(cs[i])) i++;
            int end = i - 1;
            swap(cs, start, end);
        }
        StringBuilder sb = new StringBuilder();
        for (i = 0; i < cs.length; i++) {
            if (i != 0 && cs[i] == ' ' && cs[i] == cs[i - 1]) {
                continue;
            }
            sb.append(cs[i]);
        }
        return sb.toString().trim();
    }
   
    private void swap(char[] cs, int s, int e) {
        while (s < e) {
            char tmp = cs[s];
            cs[s] = cs[e];
            cs[e] = tmp;
            s++;
            e--;
        }
    }
}

LeetCode - Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

public class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        if(s.length()!=0 && (s.charAt(0)=='-' || s.charAt(0)=='+')) s = s.substring(1);
        if(s.isEmpty()) return false;
        return isNum(s);
    }
 
    public boolean isNum(String s){
        boolean hasInteger=false, hasDot=false, hasSign=false, hasExp=false, hasExpNum=false;
        for(char c : s.toCharArray()) {
            if(c>='0' && c<='9') {
                hasInteger = true;
                if(hasExp) hasExpNum = true;
            } else if(c=='.') {
                if(!hasDot && !hasExp) hasDot = true;
                else return false;
            } else if(c=='+' || c=='-') {
                if(!hasSign && hasExp && !hasExpNum) hasSign = true;
                else return false;
            } else if(c=='e') {
                if(hasInteger && !hasExp) hasExp = true;
                else return false;
            } else return false;
        }
        if(hasInteger && (hasExp==hasExpNum)) return true;
        else return false;
    }
}

public boolean isNumber(String s) {
int i = 0, n = s.length();
while (i < n && Character.isWhitespace(s.charAt(i))) i++;
if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
boolean isNumeric = false;
while (i < n && Character.isDigit(s.charAt(i))) {
i++;
isNumeric = true;
}
if (i < n && s.charAt(i) == '.') {
i++;
while (i < n && Character.isDigit(s.charAt(i))) {
i++;
isNumeric = true;
}
}
if (isNumeric && i < n && s.charAt(i) == 'e') {
i++;
isNumeric = false;
if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
while (i < n && Character.isDigit(s.charAt(i))) {
i++;
isNumeric = true;
}
}
while (i < n && Character.isWhitespace(s.charAt(i))) i++;
return isNumeric && i == n;
}

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

public class Solution {
    public boolean isNumber(String s) {
        int i = 0, n = s.length();
        while (i < n && Character.isWhitespace(s.charAt(i))) i++;
        if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
        boolean isNumeric = false;
        while (i < n && Character.isDigit(s.charAt(i))) {
            i++;
            isNumeric = true;
        }
        if (i < n && s.charAt(i) == '.') {
            i++;
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                isNumeric = true;
            }
        }
        if (isNumeric && i < n && s.charAt(i) == 'e') {
            i++;
            isNumeric = false;
            if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                isNumeric = true;
            }
        }
        while (i < n && Character.isWhitespace(s.charAt(i))) i++;
        return isNumeric && i == n;
    }
}


========

public class Solution {
    public boolean isNumber(String s) {
        if (s == null) return false;
        int i = 0;
        int n = s.length();
        boolean numerical = false;
        while (i < n && Character.isWhitespace(s.charAt(i))) i++;
        if (i < n && (s.charAt(i) == '-' || s.charAt(i) == '+')) i++;
        while (i < n && Character.isDigit(s.charAt(i))) {
            i++;
            numerical = true;
        }
        if (i < n && s.charAt(i) == '.') {
            i++;
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                numerical = true;
            }
        }
        if (i < n && s.charAt(i) == 'e' && numerical) {
            i++;
            numerical = false;
            if (i < n && (s.charAt(i) == '+' || s.charAt(i) == '-')) i++;
            while (i < n && Character.isDigit(s.charAt(i))) {
                i++;
                numerical = true;
            }
        }
        while (i < n && Character.isWhitespace(s.charAt(i))) i++;
        return numerical && i == n;
    }
}

LeetCode - Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Have you been asked this question in an interview? 

Discuss

public class Solution {
    public double findMedianSortedArrays(int a[], int b[]) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int m = a.length;
        int n = b.length;
        int total = m + n;
        if((total)%2==1) {
            return findKth(a, 0, m, b, 0, n, total/2 + 1);
        } else {
            return (findKth(a, 0, m, b, 0, n, total/2) +
                            findKth(a, 0, m, b, 0, n, total/2 + 1))/2.0;
        }
    }

    private double findKth(int a[], int i, int m, int b[], int j, int n, int k) {
        if(m>n) {
            return findKth(b, j, n, a, i, m, k);
        }
        if(m==0)
            return b[j+k-1];
        if(k==1)
            return Math.min(a[i], b[j]);
        int pa = Math.min(k/2, m);
        int pb = k - pa;
        if(a[i+pa-1]>b[j+pb-1]) {
            return findKth(a, i, m, b, j+pb, n-pb, k - pb);
        } else if(a[i+pa-1]<b[j+pb-1]){
            return findKth(a, i+pa, m-pa, b, j, n, k - pa);
        } else {
            return a[i + pa - 1];
        }
    }
}


public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if ((m + n) % 2 == 1) {
            return findKth(nums1, 0, m, nums2, 0, n, (m + n) / 2 + 1);
        } else {
            return (findKth(nums1, 0, m, nums2, 0, n, (m + n) / 2 + 1) + findKth(nums1, 0, m, nums2, 0, n, (m + n) / 2))/2;
        }
    }
   
    public double findKth(int[] nums1, int s1, int l1, int[] nums2, int s2, int l2, int k) {
        if (l1 > l2) {
            return findKth(nums2, s2, l2, nums1, s1, l1, k);
        }
        if (l1 == 0) {
            return nums2[s2 + k -1];
        }
        if (k == 1) {
            return Math.min(nums1[s1], nums2[s2]);
        }
        int p1 = Math.min(l1, k / 2);
        int p2 = k - p1;
        if (nums1[s1 + p1 - 1] > nums2[s2 + p2 - 1]) {
            return findKth(nums1, s1, p1, nums2, s2 + p2, l2 - p2, k - p2);
        } else {
            return findKth(nums1, s1 + p1, l1 - p1, nums2, s2, p2, k - p1);
        }
    }
}

LeetCode - Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean palin[][] = new boolean[len][len];
        String maxStr = "";
        for(int i=0;i<len;i++) {
            for(int j=i;j>=0;j--) {
                palin[j][i] = s.charAt(j)==s.charAt(i) && (j+1>=i-1 || palin[j+1][i-1]);
                if(palin[j][i] && i-j+1>maxStr.length()) {
                    maxStr = s.substring(j, i+1);
                }
            }
        }
        return maxStr;
    }
}


public class Solution {
    public String longestPalindrome(String s) {
        if(s==null || s.length()<=1) return s;
        String maxS = "";
        for(int i=0;i<s.length();i++) {
            maxS = expand(s, i, i, maxS);
           // if(i!=s.length()-1)
            maxS = expand(s, i, i+1, maxS);
        }
        return maxS;
    }
   
    private String expand(String str, int s, int e, String maxS) {
        while(s>=0 && e<str.length() && str.charAt(s)==str.charAt(e)) {
            s--;
            e++;
        }
        if( e-s-1 > maxS.length() ) {
            maxS = str.substring(s+1, e);
        }
        return maxS;
    }
}


class Solution {
public:
    string longestPalindrome(string s) {
        string maxP = "";
        for(int i=0;i<s.length();i++) {
            expand(s, i, i+1, maxP);
            expand(s, i-1, i+1, maxP);
        }
        return maxP;
    }
   
    void expand(const string s, int start, int end, string &maxP) {
        while(start>=0 && end<s.length() && s[start]==s[end]) {
            start --;
            end ++;
        }
        int len = end-start-1;
        if(len>maxP.length()) {
            maxP = s.substr(start+1, end-start-1);
        }
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int min_start = 0, max_len = 1;
        for (int i = 0; i < s.size();) {
            int start = i, end = i;
            while (end < s.size()-1 && s[end+1] == s[end]) {
                end++; // Skip duplicate characters.
            }
            //i = end+1;
            i++;
            while (end < s.size()-1 && start > 0 && s[end + 1] == s[start - 1]) {
                end++;
                start--;
            } // Expand.
            int new_len = end - start + 1;
            if (new_len > max_len) {
                min_start = start;
                max_len = new_len;
            }
        }
        return s.substr(min_start, max_len);
    }
};


==========

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0, 1);
        for (int i = 1; i < s.length(); i++) {
            String s1 = getPalindrome(s, i, i);
            if (s1.length() > maxLen) {
                res = s1;
                maxLen = s1.length();
            }
            if (s.charAt(i) == s.charAt(i - 1)) {
                String s2 = getPalindrome(s, i - 1, i);
                if (s2.length() > maxLen) {
                    res = s2;
                    maxLen = s2.length();
                }
            }
        }
        return res;
    }
   
    private String getPalindrome(String str, int s, int e) {
        while (s > 0 && e < str.length() - 1 && str.charAt(s - 1) == str.charAt(e + 1)) {
            s--;
            e++;
        }
        return str.substring(s, e + 1);
    }
}

LeetCoder - Multiply Strings

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) {

        int[] arr = new int[num1.length() + num2.length()];

        for (int i = num1.length() - 1; i >= 0; i--) {

            for (int j = num2.length() - 1; j >= 0; j--) {

                int n1 = num1.charAt(i) - '0';

                int n2 = num2.charAt(j) - '0';

                arr[i + j + 1] += n1 * n2;

            }

        }

        int carry = 0;

        for (int i = arr.length - 1; i >= 0; i--) {

            int val = carry + arr[i];

            carry = val / 10;

            val = val % 10;

            arr[i] = val;

        }

        StringBuilder sb = new StringBuilder();

        boolean notZero = false;

        for (int i = 0; i < arr.length; i++) {

            if (arr[i] == 0 && !notZero) {

                continue;

            } else {

                notZero = true;

                sb.append(arr[i]);

            }

        }

        if (sb.length() == 0) return "0";

        else return sb.toString();

    }

}

Next Permutation

 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Have you been asked this question in an interview?

public class Solution {

    public void nextPermutation(int[] num) {

        // find the last ascend

        int ascend = -1;

        int smallBig = -1;

        for(int i=0;i<num.length;i++) {

            if(i!=num.length-1 && num[i]<num[i+1]) {

                ascend = i;

            }

        }

        if(ascend == -1) {

            for(int i=0;i<num.length/2;i++) {

                int tmp = num[i];

                num[i] = num[num.length-1-i];

                num[num.length-1-i] = tmp;

            }

        } else {

            for(int i=num.length-1;i>=0;i--) {

                if(num[i]>num[ascend]) {

                    smallBig = i;

                    break;

                }

            }

            

            

            int tmp = num[smallBig];

            num[smallBig] = num[ascend];

            num[ascend] = tmp;

            for(int i=ascend+1;i<num.length;i++) {

                if(i<num.length-(i-ascend)) {

                    tmp = num[i];

                    num[i] = num[num.length-(i-ascend)];

                    num[num.length-(i-ascend)] = tmp;

                } else {

                    break;

                }

            }

        }

    }

}


Next Permutation
public class Solution {
    public void nextPermutation(int[] num) {
        if(num==null || num.length==0) return;
        // find first increase from the end
        int d = -1;
        for(int i=num.length-2;i>=0;i--) {
            if(num[i]<num[i+1]) {
                d = i;
                break;
            }
        }
        if(d==-1) {
            Arrays.sort(num);
            return;
        }
        int min = Integer.MAX_VALUE;
        int minid = 0;
        for(int i=d+1;i<num.length;i++) {
            if(num[i]>num[d] && num[i]<min) {
                min = num[i];
                minid = i;
            }
        }
        // swap
        int tmp = num[d];
        num[d] = num[minid];
        num[minid] = tmp;
        // sort
        int s = d+1;
        int e = num.length-1;
        Arrays.sort(num, s, e+1);
    }
}

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

public class Solution {
    public void nextPermutation(int[] nums) {
        int firstIncrease = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                firstIncrease = i;
                break;
            }
        }
        if (firstIncrease == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        int swapIndex = firstIncrease + 1;
        for (int i = firstIncrease + 1; i < nums.length; i++) {
            if (nums[i] > nums[firstIncrease] && nums[i] <= nums[swapIndex]) {
                swapIndex = i;
            }
        }
        int tmp = nums[swapIndex];
        nums[swapIndex] = nums[firstIncrease];
        nums[firstIncrease] = tmp;
        reverse(nums, firstIncrease + 1, nums.length - 1);
    }
   
    private void reverse(int num[], int start, int end) {
        while (start < end) {
            int tmp = num[start];
            num[start] = num[end];
            num[end] = tmp;
            start++;
            end--;
        }
    }
}

Input:[2,3,1,3,3]

Expected:[2,3,3,1,3]

Permutations II

 Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Have you been asked this question in an interview?

public class Solution {

    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {

        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();

        if(num==null || num.length==0) {

            return ret;

        }

        Arrays.sort(num);

        ret.add(new ArrayList<Integer>());

        for(int n : num) {

            ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();

            HashSet<String> set = new HashSet<String>();

            for(ArrayList<Integer> lst : ret) {

                for(int i=0;i<=lst.size();i++) {

                    ArrayList<Integer> newLst = new ArrayList<Integer>(lst);

                    newLst.add(i, n);

                    StringBuilder sb = new StringBuilder();

                    for(int j : newLst) {

                        sb.append(j).append("_");

                    }

                    if(!set.contains(sb.toString())) {

                        tmp.add(newLst);

                        set.add(sb.toString());

                    }

                }

            }

            ret = tmp;

        }

        return ret;

    }

}

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

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        permutating(ans, nums, 0);
        return ans;
    }
 
    private void permutating(List<List<Integer>> ans, int[] nums, int start) {
        if (start == nums.length - 1) {
            List<Integer> li = new ArrayList<>();
            for (int n : nums) {
                li.add(n);
            }
            ans.add(li);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[start] == nums[i]) {
                continue;
            }
            swap(nums, start, i);
            permutating(ans, Arrays.copyOf(nums, nums.length), start+1);
        }
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

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


public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        permutating(ans, nums, 0);
        return ans;
    }
 
    private void permutating(List<List<Integer>> ans, int[] nums, int start) {
        if (start == nums.length - 1) {
            List<Integer> li = new ArrayList<>();
            for (int n : nums) {
                li.add(n);
            }
            ans.add(li);
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != start && nums[start] == nums[i]) {
                continue;
            }
            if (i != start)
                swap(nums, start, i);
            permutating(ans, Arrays.copyOf(nums, nums.length), start + 1);
        }
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

=======

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        boolean visit[] = new boolean[nums.length];
        helper(nums, visit, new ArrayList<Integer>(), res);
        return res;
    }
   
    private void helper(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> res) {
        if (list.size() == nums.length) {
            List<Integer> newList = new ArrayList<Integer>(list);
            res.add(newList);
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (visited[i]) {
                    continue;
                }
                if (i != 0 && nums[i] == nums[i - 1] && visited[i - 1]) {
                    continue;
                }
                list.add(nums[i]);
                visited[i] = true;
                helper(nums, visited, list, res);
                list.remove(list.size() - 1);
                visited[i] = false;
            }
        }
    }
}