Leetcode–Wildcard Matching

The Problem:

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

Notes:

  1. I used a pretty straightforward recursive solution but exceeds time limit. Here is a iterative solution, it records the index of both p and s whenever a * occurs in p, and if this round goes to a dead end, start from the recorded indices.

Java Solution

public class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
 
        if(plen==0){
            if(slen==0)return true;
            else return false;
        }
        
        int i = 0;
        int j = 0;
        int nxts = -1;
        int nxtp = -1;
//here only use i as ending condition, for the case j reach the end with no match, 
//it can go back to recorded index and match again
while(i < slen){
            if  (j < plen && (p.charAt(j)=='?' || p.charAt(j)==s.charAt(i)))
            {
                i++;
                j++;
            } 
            else if(j < plen && p.charAt(j)=='*'){
                nxtp = j;
                nxts = i;
//only increase j
                j++;
            }
            else {
                if(nxtp==-1){
                    return false;
                }
                else{
                    nxts++;
                    i = nxts;
// only increase i by 1 from previous recorded index, 
//which means include s[i] to the match of *
//(not set i up to the failure point)
                    j = nxtp+1;
                }
            }
        }
//if p has character left, only can be true if all the left are *
        while(j < plen && p.charAt(j)=='*'){
            j++;
        }
        
        return (j==plen);
   }
}
      

Leetcode–Longest Substring Without Repeating Characters

The Problem:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Notes:

  1. Check for repeating characters we can use an int or bool array of 256, no need for hash set.
  2. Remember to update the max length again when get out of while loop.

Java Solution:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length()<=1)return s.length();
        
        int start = 0;
        int end = start;
        int[] occur = new int[256];
        Arrays.fill(occur, 0);
        int maxLen = 0;
        while(start < s.length() && end < s.length()){
            if(occur[s.charAt(end)]==0){
                occur[s.charAt(end)]=1;
                end++;
            }
            else{
                maxLen = Math.max(maxLen,end-start);
                occur[s.charAt(start)]--;
                start++;
            }
        }
        maxLen = Math.max(maxLen,end-start);
        return maxLen;
    }
}

Leetcode–Partition List

The Problem:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Notes:

  1. A basic linked list question, use fake head to avoid the mess of dealing with head.
  2. Mistake I made: While nodes are all rearranged, don’t forget the set the next of tail to null, otherwise will link back to a cycle.

Java Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode fkHead = new ListNode(0);
        ListNode pre1 = fkHead;
        ListNode fkHead2 = new ListNode(0);
        ListNode pre2 = fkHead2;
        
        fkHead.next = head;
        ListNode p = head;
        while(p!= null){
            if(p.val < x){
                pre1.next = p;
                pre1 = p;
            }
            else{
                pre2.next = p;
                pre2 = p;
            }
            p = p.next;
        }
        pre1.next = fkHead2.next;
        pre2.next = null; //---!!!---important
        return fkHead.next;
    }
}

Leetcode–Multiply Strings

The Problem:

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.

Notes:

  1. The problem can be broken down to String add and String multiply by char. Multiply the first string by each character in second string from right to left, and add the result of each step.
  2. Special condition: if either input is zero then return zero, otherwise the result from multiplication would be a series of zeros.
  3. If the total number of digits of input number is less than 9, means the result can fit in a normal integer, can take them as int and do multiply.

Java Solution:

public class Solution {
    public String multiply(String num1, String num2) {
        int len1 = num1.length();
        int len2 = num2.length();
        
        if(len1 + len2 < 9){
            int res = Integer.parseInt(num1) * Integer.parseInt(num2);
            return String.valueOf(res);
        }
        if(num1.equals("0") || num2.equals("0"))return "0";
        String res = "0";
        for(int i = 0; i < len2; i++){
            String mult = multByChar(num1, num2.charAt(len2-1-i));
            int k = i;
            while(k>0){
                k--;
                mult = mult+"0";
            }
            res = addStr(mult, res);
        }
        return res;
    }
    
    private String addStr(String a, String b){
        int lena = a.length();
        int lenb = b.length();
        int len = Math.max(lena, lenb)+1;
        char[] res = new char[len];
        int carry = 0;
        int i;
        for(i = 1; i <= Math.min(lena, lenb); i++){
            int sum = (a.charAt(lena-i)-'0') + (b.charAt(lenb-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
        }
        while(i<=lena){
            int sum = (a.charAt(lena-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
            i++;
        }
        while(i<=lenb){
            int sum = (b.charAt(lenb-i)-'0')+carry;
            res[len-i] = (char)(sum%10+'0');
            carry = sum/10;
            i++;
        }
        if(carry==0){
            return new String(res).substring(1);
        }
        else{
            res[0] = (char)(carry+'0');
            return new String(res);
        }
    }
    
    private String multByChar(String num, char ch){
        if(ch=='0') return "0";
        int len = num.length();
        char[] res = new char[len+1];
        int carry = 0;
        int mul = ch-'0';
        for(int i = 0; i < len; i++){
            int pro = mul * (num.charAt(len-1-i)-'0') + carry;
            res[len-i] = (char)(pro%10+'0');
            carry = pro/10;
        }
        if(carry == 0){
            return new String(res).substring(1);
        }
        else{
            res[0] =(char)(carry+'0');
            return new String(res);
        }
    }
}

Leetcode–Merge Two Sorted Lists

The Problem:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Notes:

  1. Simple question just similar to Merge two sorted array.

Java Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        
        ListNode fkHead = new ListNode(0);
        ListNode pre = fkHead;
        while(l1!= null && l2 != null){
            if(l1.val < l2.val){
                pre.next = l1;
                pre = l1;
                l1 = l1.next;
            }
            else{
                pre.next = l2;
                pre = l2;
                l2=l2.next;
            }
        }
        if(l1!=null){
            pre.next = l1;
        }
        if(l2!= null){
            pre.next = l2;
        }
        return fkHead.next;
    }
}

Leetcode–Merge Sorted Array

The Problem:

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

Notes:

  1. Simple merge sort, note that we are doing it in space, so start from the end because we have of extra space there.

Java Solution:

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int k = m+n-1; 
        int i = m-1;
        int j = n-1;
        while(k >=0){
            if (i>=0 && j>=0){
                if(A[i] < B[j]){
                    A[k] = B[j];
                    j--;
                }
                else{
                    A[k] = A[i];
                    i--;
                }
            }
            else if(i>=0){
                A[k] = A[i];
                i--;
            }
            else if(j>=0){
                A[k] = B[j];
                j--;
            }
            else{
                break;
            }
            k--;
        }
    }
}

Leetcode–Add Binary

The Problem:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

 

Notes:

  1. Similar to Add Two Numbers, implement a adder with carry so does not matter if binary or hex or decimal.
  2. Be careful don’t forget the last carry when all nodes traversed, should add one more node for carry.

Java Solution:

public class Solution {
    public String addBinary(String a, String b) {
        int lena = a.length();
        int lenb = b.length();
        int len = Math.max(lena, lenb)+1;
        char[] res = new char[len];
        int i = 1;
        int carry = 0;
        while(i<=lena && i <= lenb){
            char ach = a.charAt(lena-i);
            char bch = b.charAt(lenb-i);
            int sum =  (ach-'0')+(bch-'0')+carry;
            res[len-i] =(char)(sum%2 + '0');
            carry = sum/2;
            i++;
        }
        while(i <= lena){
            char ach = a.charAt(lena-i);
            int sum =  (ach-'0')+carry;
            res[len-i] =(char)(sum%2 + '0');
            carry = sum/2;
            i++;

        }
        while(i <= lenb){
            char bch = b.charAt(lenb-i);
            int sum =  (bch-'0')+carry;
            res[len-i] =(char)(sum%2 + '0');
            carry = sum/2;
            i++;

        }
        if(carry!= 0){
            res[len-i] = '1';
            return new String(res);
        }
        else{
            return new String(res).substring(1);
        }
    }
}