czxttkl

'A' -> 1
'B' -> 2
...
'Z' -> 26

Code

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or s.startswith('0'):
            return 0
            
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 1

        for i in xrange(1, len(s)):
            if 1 <= int(s[i]) <= 9:
                dp[i+1] += dp[i]
            if 10 <= int(s[i-1:i+1]) <= 26:
                dp[i+1] += dp[i-1]

        return dp[-1]

Idea

Use 1D DP. dp[0] means an empty string will have one way to decode, dp[1]means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.

Reference: https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation

I was initially trying the following code. However this easily time limits when the input string is long:

class Solution(object):
    def __init__(self):
        self.res = 0

    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        self.helper(s)
        return self.res
    
    def helper(self, s):
        if s.startswith('0'):
            return
        
        if len(s) == 1:
            self.res += 1
        elif len(s) == 2:
            if int(s) <= 26:
                self.res+= 1
            self.helper(s[1:])
        else:
             self.helper(s[1:]) 
             if int(s[:2]) <= 26:
                 self.helper(s[2:]) 

Code

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if len(b) > len(a):
            a, b = b, a
        b = '0' * (len(a)-len(b)) + b

        carry = 0
        res = ['0'] * (len(a))

        for idx, (i,j) in enumerate(zip(a[::-1], b[::-1])):
            tmp = i + j + carry
            if tmp < 2:
                res[-idx-1] = str(tmp)   
            else:
                res[-idx-1] = str(tmp % 2)
                carry = 1

        # result cannot be longer than len(a)+1
        if carry:
            return str(carry) + ''.join(res)
        else:
            return ''.join(res)

Idea

From right to left, add each position. 

Code

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        # maintain how many zeroes we have seen
        count0 = 0

        for idx, v in enumerate(nums):
            if v != 0:
                if count0 > 0:
                    nums[idx-count0] = v
                    nums[idx] = 0
            else:
                count0 += 1

Idea

An element should be moved count0 ahead, where count0 records how many zeroes we have seen.

If the order of non-zero elements is not required to maintain, we can have another algorithm:

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        
        start, end = 0, len(nums)-1
        while start < end:
            if nums[start] == 0:
                nums[start], nums[end] = nums[end], nums[start]
                end -= 1
            else:
                start += 1

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

Code

class Solution(object):

    def __init__(self, nums):
        """
        
        :type nums: List[int]
        :type numsSize: int
        """
        self.nums = nums
        

    def pick(self, target):
        """
        :type target: int
        :rtype: int
        """
        count = 0
        for idx, v in enumerate(self.nums):
            if v == target:
                count += 1
                if random.randrange(count) == 0:
                    res = idx
        return res


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)

Idea

Reservoir Sampling. O(n) time and O(1) space. n is the length of nums.

Reference

https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution

If someone requires O(1) pick speed, one can construct a dictionary recording indices in __init__. See: https://discuss.leetcode.com/topic/58635/o-n-constructor-o-1-pick-two-ways

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Code

from collections import defaultdict

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = defaultdict(list)
        for s in strs:
            # you can also use tuple(sorted(s)) as dictionary key
            ss = ''.join(sorted(s))
            res[ss].append(s)
            
        return res.values()

Idea

Sort every string. Therefore, anagrams will always result in the same sorted string. Using the sorted string as key in dictionary so all anagrams will be grouped under the same key.

The time complexity is O(N MlogM), where $latex N$ is the length of strs and $latex M$ is the maximum length of single string in strs .  

Another idea is to hash every string such that a anagram group can be hashed into the same value. One way is to use prime numbers: https://discuss.leetcode.com/topic/12509/o-m-n-algorithm-using-hash-without-sort. However, this method may incur overflow.

General Idea:

You need to first flip matrix upside down. Then swap elements mirror to the diagonal.

<span class="hljs-comment"> # clockwise rotate
 # first reverse up to down, then swap the symmetry 
 # 1 2 3     7 8 9     7 4 1
 # 4 5 6  => 4 5 6  => 8 5 2
 # 7 8 9     1 2 3     9 6 3</span>

Code

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        matrix[:] = zip(*matrix[::-1])
        

Idea

Pythonic way. 

Code

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        
        self.upside_down(matrix)
        self.mirror_diag(matrix)

    def upside_down(self, matrix):
        n = len(matrix)
        for i in xrange(n/2):
            for j in xrange(n):
                matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]

    def mirror_diag(self, matrix):
        n = len(matrix)
        for i in xrange(n):
            for j in xrange(i+1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

Idea

Self implement upside down and mirror.

Reference:

https://discuss.leetcode.com/topic/15295/seven-short-solutions-1-to-7-lines

https://discuss.leetcode.com/topic/6796/a-common-method-to-rotate-the-image/2

Code

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        pre = 0
        sum = 0
        mapping = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000} 
        for ch in s[::-1]:
            i = mapping[ch]
            if i >= pre:
                sum += i
            else:
                sum -= i
            pre = i

        return sum

Idea

Fun to know how to read Roman number!

Reference: 

https://discuss.leetcode.com/topic/821/my-solution-for-this-question-but-i-don-t-know-is-there-any-easier-way/2 (Answer from vera_qing)

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Code

from collections import deque 
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "": return []
        
        mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = deque([''])
        for i in digits:
            for j in xrange(len(res)):
                s = res.popleft()
                for k in mapping[int(i)]:
                    res.append(s + k)
        
        return list(res)

Idea

Use a FIFO queue. Therefore, we can maximally reduce extra space needed.

Reference: https://discuss.leetcode.com/topic/8465/my-java-solution-with-fifo-queue

Code

from collections import deque 
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "": return []
        
        mapping = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        return reduce(lambda acc, d: [x+y for x in acc for y in mapping[int(d)]], digits, [''])

Idea 

Pythonic way using reduce.

Reference: https://discuss.leetcode.com/topic/11783/one-line-python-solution

https://leetcode.com/problems/3sum-closest/

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Code

import sys

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums = sorted(nums)
        min_diff = sys.maxint
         
        for i in xrange(len(nums)-2):
            j = i + 1
            k = len(nums)-1
            while j < k:
                cur_sum = nums[i] + nums[j] + nums[k]
                cur_diff = abs(cur_sum - target)
                if cur_diff < min_diff:
                     res = cur_sum
                     min_diff = cur_diff
                if cur_sum > target:
                     k -= 1
                elif cur_sum < target:
                     j += 1
                else:
                     return res

        return res

Idea

Sort the array first. Then, create three pointers, i, j and k, such that, when i is fixed, j and k are adjusted to make the 3sum approach the target. The total time complexity is O(N^2) where N is the length of nums.

Code 

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        M = ["", "M", "MM", "MMM"]
        C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10]

Idea

Nothing much.