Question

link

P   A   H   N
A P L S I I G
Y   I   R

string convert(string text, int nRows);

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

Two ways to work out this problem.

Solution 1. Insert string s vertically into a 2d array, char by char. After this is finished, make the result string by reading the 2d array horizontally. See code 1 below.

Solution 2. Calculate and find out (in sequence) which char from s should be inserted into the result list. Then build the result list directly. See code 2 below.

My code

One. Fill in the whole string, then parse the result.

public class Solution {
    public String convert(String s, int nRows) {
        if (s == null || s.length() == 0 || nRows < 1) {
            return "";
        } else if (nRows == 1) {
            return s;
        }
        int len = s.length();
        int grpSize = nRows * 2 - 2;
        int numGrp = (len - 1) / grpSize + 1;
        String[][] array = new String[nRows][numGrp * 2];
        // fill in string s into array, one group after another
        int p = 0;
        // for each group
        for (int i = 0; i < numGrp; i++) {
            // for each vertical index (left col), fill in one letter from s
            for (int j = 0; j < nRows; j++) {
                // if s is used up, break
                if (p == len) {
                    break;
                }
                array[j][i * 2] = "" + s.charAt(p);
                p++;
            }
            // for each vertical index (right col), fill in one letter from s
            for (int j = nRows - 2; j > 0; j--) {
                // if s is used up, break
                if (p == len) {
                    break;
                }
                array[j][i * 2 + 1] = "" + s.charAt(p);
                p++;
            }
        }
        // now convert array[][] into final string and return answer
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[0].length; j++) {
                if (array[i][j] == null || array[i][j].length() == 0) {
                    continue;
                } else {
                    sb.append(array[i][j]);
                }
            }
        }
        return sb.toString();
    }
}

Two. Pick the correct char and form the result string, and fill it in the result string.

public class Solution {
    public String convert(String s, int nRows) {
        if (nRows <= 1)
            return s;
        int eachPattern = 2 * nRows - 2;
        int numPatterns = (s.length() - 1) / eachPattern + 1;
        StringBuilder ans = new StringBuilder();
        for (int j = 0; j < nRows; j++) {
            for (int i = 0; i < numPatterns; i++) {
                ans.append(find(s, eachPattern, i, j));
                if (j != 0 && j != nRows - 1)
                    ans.append(find(s, eachPattern, i, 2 * (nRows - 1) - j));
            }
        }
        return ans.toString();
    }

    private String find(String s, int eachPattern, int i, int j) {
        // find (j)th element from (i)th pattern
        int temp = eachPattern * i + j;
        if (temp < s.length())
            return s.substring(temp, temp + 1);
        return "";
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is not difficult, but hard to get it right. Remember to handle all cases listed below:

1. null or empty string
2. white spaces
3. +/- sign
4. calculate real value
5. return int.min or int.max

Solution

Use one loop to read through, and in the end do some checking. There is a very good explanation from online.

This is a standard string question, and try think of some special test cases.

My code

public class Solution {
    public int atoi(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        int p = 0; 
        int len = str.length();
        // omit as many space as possible
        while (p < len) {
            if (str.charAt(p) != ' ') {
                break;
            }
            p++;
        }
        int sign = 1;
        // check if there is a +/- sign at position p
        // if there is, store its value and advance p
        if (p == len) {
            return 0;
        } else if (str.charAt(p) == '+') {
            p++;
        } else if (str.charAt(p) == '-') {
            sign = -1;
            p++;
        }
        // check if position p have valid number
        if (p == len) {
            return 0;
        } else if (str.charAt(p) < '0' || str.charAt(p) > '9') {
            return 0;
        }
        // now position p is the start of numerical part.
        int q = p;
        while (q < len && str.charAt(q) >= '0' && str.charAt(q) <= '9') {
            q++;
        }
        String numPart = str.substring(p, q);
        // first, check if numPart is too long
        if (numPart.length() > 15) {
            if (sign == -1) {
                return Integer.MIN_VALUE;
            } else {
                return Integer.MAX_VALUE;
            }
        }
        // second, convert to numerical format and check value against Integer.MIN and MAX
        long num = sign * Long.parseLong(numPart);
        if (num > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        } else if (num < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        } else {
            return (int) num;
        }
    }
}

Question

link

'.' 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

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Very important to note: Do not use DP. Why? Because eg. “a*b” will be considered as 2 parts: “a*” part and “b” part. Because star is considered to be bundled with previous char, it gives us difficulty in determine the size of the DP array. Of course, we still can do it, but I see nobody have provided a nice DP solution online. Let’s just forget about it for now.

The solution I’m giving in this post, is to trim String and compare.

We only need to consider 2 cases:

One, the next char is NOT a star sign. This requires simply char compare.

Two, the next char is a star sign, this will require some effort.

Solution

In case of one letter bundled with a star sign, we iterate thru all possible number of repetition of current char (from 0 until large), and check validation one by one.

A final important note, this question very much looks like DP, but NOT DP.

My code

My code.

public class Solution {
    public boolean isMatch(String s, String p) {
        // eg. s = "aab"  p = "c*a*b"
        return check(s, p, 0, 0);
    }

    private boolean check(String s, String p, int start1, int start2) {
        int len1 = s.length();
        int len2 = p.length();
        if (start1 == len1 && start2 == len2) {
            return true;
        } else if (start2 == len2) {
            // if p is used up, but still some letters left in s
            return false;
        }
        // check if there is * after start2 in p
        if (start2 == len2 - 1 || p.charAt(start2 + 1) != '*') {
            // if there is no *
            // match only 1 char
            if (start1 == len1) {
                // unable to match single char because s is fully used up
            } else if (p.charAt(start2) != '.' && s.charAt(start1) != p.charAt(start2)) {
                // if single char could not be matched
                return false;
            } else {
                // if single letter matches
                return check(s, p, start1 + 1, start2 + 1);
            }
        } else {
            // if there is a * following start2
            if (check(s, p, start1, start2 + 2)) {
                // the letter in p represent 0 chars
                return true;
            } else {
                // the letter in p represent 1 or more chars
                // advance start1 until the end of s
                while (start1 < len1) {
                    // check if the char matches
                    if (p.charAt(start2) != '.' && s.charAt(start1) != p.charAt(start2)) {
                        break;
                    }
                    if (check(s, p, start1 + 1, start2 + 2)) {
                        return true;
                    }
                    start1++;
                }
            }
        }
        return false;
    }
}

A much shorter version from someone else making use of String.substring(). I refactored a bit.

public class Solution {
    public boolean isMatch(String s, String p) {
        // s is normal string, and p is regex string
        if (p.length() == 0) {
            return s.length() == 0;
        } else if (p.length() < 2 || p.charAt(1) != '*') {
            // if 2nd char in p is not '*', then match character
            if (s.length() == 0) {
                return false;
            } else if (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)) {
                return false;
            } else {
                return isMatch(s.substring(1), p.substring(1));
            }
        } else {
            // if 2nd char in p is '*', then iterate all position repetitions
            char repeatLetter = p.charAt(0);
            for (int i = 0; i <= s.length(); i++) {
                // i is the number of repetition of repeatLetter, start from 0
                if (i > 0 && repeatLetter != s.charAt(i - 1)
                        && repeatLetter != '.') {
                    break;
                } else {
                    if (isMatch(s.substring(i), p.substring(2))) {
                        return true;
                    }
                }
            }
            return false;
        }
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is easy, and very similar to the “Reverse Integer” question. Simpliest solution is to just reverse the integer and compare with original number.

But again, reversing the integer have chances of overflow. How do we work this out?

Solution

First, same as previous post [LeetCode 7] Reverse Integer, we can use Long type to handle the overflow issues.

Second, we can also do direct compare to always compare the head and tail of the number. No numerical type conversion is needed. I came up with idea previously, and code is posted below.

My code

Use Long type:

public class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }
        long rev = 0;
        long original = x;
        while (x != 0) {
            rev = rev * 10 + (x % 10);
            x = x / 10;
        }
        return original == rev;
    }
}

Compare head and tail:

public boolean isPalindrome(int x) {
    if (x < 0) {
        return false;
    }
    int divide = 1;
    while (x / divide >= 10) {
        divide *= 10;
    }
    int head = 0, tail = 0;
    while (divide > 0) {
        head = x / divide;
        tail = x % 10;
        if (head != tail) {
            return false;
        }
        x = x % divide / 10;
        divide /= 100;
    }
    return true;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

Assume i and j are 2 points in x-axis where i < j. The container volume is decided by the shorter height among the two.

Assume i is lower than j, there will be no i < jj < j that makes the area of (i,jj) greater than area of (i,j). In other words, all (i,jj) is smaller than (i,j) so there’s no need to check them.

Thus we move i forward by 1. This idea is explained in this post.

Solution

Two-pointer scan. And always move the shorter board index (if we consider it to be a rectangle bucket), as explained in this post.

My code

public class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        // start calculating area and shrinking the distance 
        // between left and right pointer
        while (left < right) {
            area = Math.max(area, (right - left) 
                * Math.min(height[left], height[right]));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There’re 2 points that are tricky.

First, overflow issue. Look at the following overflow case for Java int:

+300,000,000 * 10 returns -1294967296
+600,000,000 * 10 returns +1705032704
-300,000,000 * 10 returns +1294967296
-600,000,000 * 10 returns -1705032704
note that max integer is 2,147,483,647

We can observe that if overflow happens, the result is definitely wrong. The result can be either positive or negative.

So, from just +/- sign of the result, we can’t identify an overflow (then how to solve this problem??).

Another interesting thing to note: we actually do not need to handle negative sign. The sign can be preserved during the conversion. Read this post for more.

Without considering overflow, the following code can (almost) work fine:

public int reverse2(int x) {
    int reverse = 0;
    while (x != 0) {
        reverse = reverse * 10 + x % 10;
        x /= 10;
    }
    return reverse;
}

Solution

Two solutions: 1. use long data type. 2. check if ret > 214748364 or ret < –214748364 before multiplying by 10.

My code

First, using long type to avoid overflow.

public class Solution {
    public int reverse(int x) {
        int sign = 1;
        long abs = x;
        long rev = 0;
        if (x < 0) {
            sign = -1;
            abs = 0 - abs;
        }
        // now remove numbers from abs one by one
        // and put these numbers into rev
        while (abs != 0) {
            rev *= 10;
            rev += abs % 10;
            abs /= 10;
        }
        if (rev > Integer.MAX_VALUE) {
            return 0;
        } else {
            return sign * (int) rev;
        }
    }
}

Second, do boundary check in every step. Suggested by Leetcode official book.

Note that max integer is 2,147,483,647

public class Solution {

    public int reverse(int x) {
        int ret = 0;
        while (x != 0) {
            // handle overflow/underflow
            if (Math.abs(ret) > 214748364) {
                return 0;
            }
            ret = ret * 10 + x % 10;
            x /= 10;
        }
        return ret;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

There are 2 solutions. One is DP which is O(N²) time and O(N²) space. Another is “Search around corner”, which uses less space.

Solution

DP solution is straight-forward. Use 2D array to check palindrome intervals and make it as either true or false. Meanwhile, update longest.

O(N²) time and O(N²) space

Search around corner is basically iterate through the entire string and assume each char (or char pair) as center of the palindrome. The code isn’t difficult once you come up with the idea.

For more, read this post

O(N²) time and O(1) space

My code

DP solution

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        String longest = "";
        int len = s.length();
        // dp[i][j] means substring of s from i to j is palindrome 
        boolean[][] dp = new boolean[len][len];
        // why i decrease from (len-1) to 0, but j increase from i to (len-1)?
        // think about it! 
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else if (i + 1 == j) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    // important to note: dp[i+1][j-1]
                    // i depends on (i+1), so i from large to small
                    // j is just the opposite, small to large
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
                if (dp[i][j] && j + 1 - i > longest.length()) {
                    longest = s.substring(i, j + 1);
                }
            }
        }
        return longest;
    }
}

Search around corner

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1)
            return s;
        String largest = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String first = this.searchAroundCenter(s, i, i);
            String second = this.searchAroundCenter(s, i, i + 1);
            if (first.length() < second.length())
                first = second;
            if (largest.length() < first.length())
                largest = first;
        }
        return largest;
    }

    private String searchAroundCenter(String s, int a, int b) {
        if (a < 0 || b > s.length() - 1)
            return "";
        while (s.charAt(a) == s.charAt(b)) {
            a--;
            b++;
            if (a < 0 || b > s.length() - 1)
                return s.substring(a + 1, b);
        }
        return s.substring(a + 1, b);
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question looks easy (well, isn’t it?), but it really is not easy!.

The main idea is: an array of int(128) is used to keep track of the last occurance position of each character. So we iterate thru the characters while constently checking the last occurrence of the letter. Meanwhile, keep updating the longest distance.

There is 1 place where it’s extremely easy to make mistake, that is the condition of update left points:

if (previousPos != -1&& previousPos >= left) {
    left = previousPos + 1;
}

If you have an idea of using array int(128) to store last occurrence, and you got the above if condition correct, then you nailed it!

Again, this is a tough question. There’s a seemingly more intuitive solution using the sliding window method. It’s very similar to [LeetCode 76] Minimum Window Substring.

Solution

Note what happens when a repeating char is found (2 different conditions).

My code

The proper way:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int[] flag = new int[128];
        for (int i = 0; i < flag.length; i++) {
            flag[i] = -1;
        }
        // left and right pointer defines the valid range
        int left = 0;
        int right = 0;
        int longest = 0;
        int len = s.length();

        while (right < len) {
            char letter = s.charAt(right);
            int previousPos = flag[letter];
            if (previousPos != -1&& previousPos >= left) {
                // if right pointer points to an old letter, and is within current range
                // then we need to update our left pointer: 
                // to bypass the previous occurrence of that letter
                left = previousPos + 1;
            }
            flag[letter] = right;
            // advance right pointer to the next letter, and calculate longest distance
            right++;
            longest = Math.max(longest, right - left);
        }
        return longest;
    }
}

The sliding window way:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int left = 0;
        int right = 1;
        HashSet<Character> set = new HashSet<Character>();
        set.add(s.charAt(0));
        int longest = 1;
        while (right < len) {
            // right pointer proceeds until boundary or duplicate char found
            while (right < len && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
                longest = Math.max(longest, right - left);
            }
            if (right == len) {
                return longest;
            } else {
                // right pointer has reached a duplicate char.
                // now move left pointer until that dup char is found
                while (s.charAt(left) != s.charAt(right)) {
                    set.remove(s.charAt(left));
                    left++;
                }
                // left pointer advance by one to bypass the dup char
                left++;
                // right pointer advance by one to include the dup char
                right++;
            }
        }
        return Math.max(longest, right - left);
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This question is straight-forward. Just add one by one with a carry bit.

My code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return helper(l1, l2, 0);
    }

    private ListNode helper(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null) {
            if (carry == 0) {
                return null;
            } else {
                return new ListNode(1);
            }
        } else if (l1 == null) {
            return helper(new ListNode(0), l2, carry);
        } else if (l2 == null) {
            return helper(l1, new ListNode(0), carry);
        } else {
            // both l1 and l2 have value
            int sum = l1.val + l2.val + carry;
            int resultNumber = sum % 10;
            int newCarry = sum / 10;
            ListNode ans = new ListNode(resultNumber);
            ans.next = helper(l1.next, l2.next, newCarry);
            return ans;
        }
    }
}

Instead of doing it recursively, someone write a nice code for an iterative 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 addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode res = new ListNode(0);
        ListNode cur1 = l1, cur2 = l2, head = res;
        while (cur1 != null || cur2 != null) {
            if (cur1 != null) {
                carry += cur1.val;
                cur1 = cur1.next;
            }
            if (cur2 != null) {
                carry += cur2.val;
                cur2 = cur2.next;
            }
            head.next = new ListNode(carry % 10);
            head = head.next;
            carry /= 10;
        }
        if (carry == 1)
            head.next = new ListNode(1);
        return res.next;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

It’s not a good idea to sort the input, because we are supposed to return the position index. Without sorting, we must use some data structure to help us!

And the answer is HashMap.

Solution

Read thru the list of integers, and each time add (targer - curInt) to the hashmap.

If the number is contained in the HashMap, solution found.

My code

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        if (numbers == null || numbers.length == 1) {
            return result;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(numbers[i])) {
                result[0] = map.get(numbers[i]) + 1;
                result[1] = i + 1;
                return result;
            } else {
                // put <key, value> into hashmap where key is the number 
                // that would complement the sum to be target. Like this: 
                map.put(target - numbers[i], i);
            }
        }
        return result;
    }
}