czxttkl

https://leetcode.com/problems/shortest-word-distance-iii/

Code

import sys
class Solution(object):
    def shortestWordDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        
        min_dis = sys.maxint
        p1, p2 = min_dis, -min_dis
        for i in xrange(len(words)):
            w = words[i]
            if w not in set([word1, word2]):
                continue
            if word1 == word2:
                p1 = p2
                p2 = i
            else:
                if w == word1:
                    p1 = i
                if w == word2:
                    p2 = i
           
            min_dis = min(min_dis, abs(p1 - p2))
        
        return min_dis

Idea

A little similar to the previous post. The only difference is that, if word1==word2, then we need to set `p1` to previous `p2`, and set `p2` to current `i`. We keep unchanged how `min_dis` is determined: min(min_dis, abs(p1 – p2)) 

https://leetcode.com/problems/shortest-word-distance-ii/

Code

class WordDistance(object):
    def __init__(self, words):
        """
        initialize your data structure here.
        :type words: List[str]
        """
        word_dic = dict()
        for i in xrange(len(words)):
            w = words[i]
            if word_dic.get(w, None):
                word_dic[w].append(i)
            else:
                word_dic[w] = [i]
        self.word_dic = word_dic

    def shortest(self, word1, word2):
        """
        Adds a word into the data structure.
        :type word1: str
        :type word2: str
        :rtype: int
        """
        l1 = self.word_dic[word1]
        l2 = self.word_dic[word2]
        min_dis = sys.maxint
        p1 = 0
        p2 = 0
        while p1 < len(l1) and p2 < len(l2):
            min_dis = min(min_dis, abs(l1[p1]-l2[p2]))
            if min_dis == 1:
                 return 1            
            if l1[p1] > l2[p2]:
                p2 += 1
            else:
                p1 += 1
        return min_dis

        

# Your WordDistance object will be instantiated and called as such:
# wordDistance = WordDistance(words)
# wordDistance.shortest("word1", "word2")
# wordDistance.shortest("anotherWord1", "anotherWord2")

Idea

Since the function `shortest` will be called repeatedly, we need to use more space in trade of less time. We know from the previous post that if we don’t use any space we can have an O(N) algorithm. Therefore, in this problem, we want to achieve shorter time than O(N) by using more space.

What we do is just using a dictionary to store positions for words. (key: word, value: a list of positions in `words` where the word appears). Since we traverse from words[0] to words[-1], we guarantee every position list stores positions in an ascending order. Then, when we call `shortest(words, word1, word2)`. we extract `word1`’s and `word2`’s position lists. 

The crux of the algorithm is that if p1 (a position from word1’s position list) is already larger than p2 (a position from word2’s position list), then every position after p1 in the word1’s position list will have larger distance with p2. Therefore, you don’t need to compare those positions after p1 anymore. Instead, you increase p2 in order to let it be closer to p1.

The time complexity is O(m+n) where m and n are the lengths of l1 and l2. 

Reference: https://discuss.leetcode.com/topic/20643/java-solution-using-hashmap

https://leetcode.com/problems/shortest-word-distance/

Code

import sys
class Solution(object):
    def shortestDistance(self, words, word1, word2):
        """
        :type words: List[str]
        :type word1: str
        :type word2: str
        :rtype: int
        """
        p1 = p2 = -1
        min_dis = sys.maxint
        for i in xrange(len(words)):
            w = words[i]
            if w not in [word1, word2]:
                continue
            if w == word1:
                p1 = i
            if w == word2:
                p2 = i
            if p1 != -1 and p2 != -1:
                min_dis = min(min_dis, abs(p1 - p2))
        
        return min_dis

Idea

Just need O(N) time to traverse the `word` list once. `p1` and `p2` are the last index of seeing word1 and word2. If the current visit word is either word1 or word2, you can update the min distance just by `abs(p1-p2)`.

https://leetcode.com/problems/different-ways-to-add-parentheses/

((2-1)-1) = 0
(2-(1-1)) = 2

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Code

class Solution(object):
    def diffWaysToCompute(self, input):
        if input.isdigit():
            return [int(input)]
        res = []        
        for i in xrange(len(input)):
            if input[i] in "-+*":
                res1 = self.diffWaysToCompute(input[:i])
                res2 = self.diffWaysToCompute(input[i+1:])
                res += [eval(str(k)+input[i]+str(j)) for k in res1 for j in res2]            
        return res

Idea

Deal it with recursion. Whenever you see an operator (`-`, `+` or `*`), you get results from the operator’s left side (line 8) and right side (line 9) and concatenate results from both sides with the operator (line 10) . Remember that to judge if a string represents a pure number you can use `string.isdigit()`. (line 3)

Reference

https://leetcode.com/discuss/53566/python-easy-to-understand-solution-divide-and-conquer

https://leetcode.com/problems/generate-parentheses/

Code

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        res = []
        def gen(s, left, right, res):
            if left:
                gen(s+"(", left-1, right, res)
            if right > left:
                gen(s+")", left, right-1, res)
            if not right:
                res += [s]
        gen("", n, n, res)
        return res

Idea

Use recursion to solve this problem. You can also apply this idea to other similar problems, such as print “if else” blocks.

Another variant is that if you know the result of `generateParenthesis(n)` (a list of valid strings), then you can know `generateParenthesis(n+1)` by concatenating “()” in front of all strings in `generateParenthesis(n)`, or add “(” and “)” at the beginning and the end of all strings in `generateParenthesis(n)`.

https://leetcode.com/problems/perfect-squares/

Code 1:

from collections import deque
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case 1
        if n < 0:
            return -1
        # corner case 2
        if n==0:
            return 1
    
        q = deque()         
        visited = set()
        # val, step
        q.append((0,0))
        visited.add(0)

        while q:
            val, step = q.popleft()    
            for i in xrange(1, n+1):
                tmp = val + i**2
                if tmp > n:
                    break
                if tmp == n:
                    return step+1
                else:
                    if tmp not in visited:
                        visited.add(tmp)
                        q.append((tmp, step+1))                 
        
        # Should never reach here
        return -1   

Idea 1:

Use BFS to solve this problem. We can think of a tree graph in which nodes are value 0, 1,…,n. A link only exists between i and j (i<j) if j=i+square_num. We start from node 0 and add all nodes reachable from 0 to queue. Then we start to fetch elements from the queue to continue to explore until we reach node n. Since BFS guarantees that for every round all nodes in the queue have same depth, so whenever we reach node n, we know the least depth needed to reach n, i.e., the least number of square number to add to n.

Don’t forget to use a set `visited` to record which nodes have been visited. A node can be reached through multiple ways but BFS always makes sure whenever it is reached with the least steps, it is flagged as visited.

Why can’t we use DFS? Why can’t we report steps when we reach n by DFS? Because unlike BFS, DFS doesn’t make sure you are always using the least step to reach a node. Imagine DFS may traverse all nodes to reach n becaues each node is its previous node plus one (because one is a square number.) When you reach n, you use n steps. But it may or may not be the least number required to reach n.

This teaches us a lesson that if you want to find “….’s least number to do something”, you can try to think about solving it in BFS way.

Code 2:

import sys
import itertools
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case 1
        if n < 0:
            return -1
        # corner case 2
        if n==0:
            return 1
    
        dp = [sys.maxint]*(n+1)
        dp[0] = 0

        for i in xrange(1, n+1):
            tmp = dp[i]
            for j in xrange(1, n+1):
                if j**2 > i:
                    break
                tmp = min(tmp, 1 + dp[i-j**2])
            dp[i] = tmp

        return dp[-1]

Idea 2:

Just normal DP. Leetcode actually reported TLE for this version. I guess it will pass if written in other language but with the same idea.

Reference

https://leetcode.com/discuss/57380/python-common-bfs-with-fewer-lines

https://docs.python.org/2/tutorial/datastructures.html

https://leetcode.com/problems/sqrtx/

Code

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            return -1
        
        left, right = 0, x
        while left <= right:
            mid = left + (right - left)/2
            if mid**2 < x:
                left = mid + 1
            elif mid**2 > x:
                right = mid - 1
            else:
                return mid
        
        return left-1    
        

Idea

Binary Search

https://leetcode.com/problems/power-of-two/

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return (n & (n-1)) == 0 and n > 0
        

Idea:

Using the idea that if a number is power of two, its binary format should be: `1000..`. Then the number subtracted one should be: `011111..`. So `(n&(n-1))==0` can be used to judge if a number if power of two. 

An follow up is to calculate number k to the power of n: power(n, k). You can see how to use divide and conquer to solve this problem in `O(logN)`: http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/, https//nb4799.neu.edu/wordpress/?p=1078

https://leetcode.com/problems/integer-to-english-words/

123 -> "One Hundred Twenty Three"
12345 -> "Twelve Thousand Three Hundred Forty Five"
1234567 -> "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Code (https://leetcode.com/discuss/55477/recursive-python):

def numberToWords(self, num):
    to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
           'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
    tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
    def words(n):
        if n < 20:
            return to19[n-1:n]
        if n < 100:
            return [tens[n/10-2]] + words(n%10)
        if n < 1000:
            return [to19[n/100-1]] + ['Hundred'] + words(n%100)
        # p starts from 1
        for p, w in enumerate(('Thousand', 'Million', 'Billion'), 1):
            if n < 1000**(p+1):
                return words(n/1000**p) + [w] + words(n%1000**p)
    return ' '.join(words(num)) or 'Zero'

Idea:

Just use a recursive function to solve this problem. Nothing much to say.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Code

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if not prices or not k:
            return 0
        if k >= len(prices)/2:
            profit = 0
            for i in xrange(1, len(prices)):
                if prices[i] - prices[i-1] > 0:
                    profit += prices[i] - prices[i-1]
            return profit

        profit = [[0] * len(prices) for _ in xrange(k+1)]        
        for i in xrange(1, k+1):
            tmp = -prices[0]
            for j in xrange(1, len(prices)):
                profit[i][j] = max(profit[i][j-1], tmp + prices[j])
                tmp = max(tmp, profit[i-1][j-1] - prices[j])
        
        return profit[-1][-1]
        

Idea

First of all, let’s deal with the case where `k >= len(prices)/2`. In this case, you can use at most `k` transactions to get profits in all ascending intervals of prices. You can imagine an extreme case where the prices go like this:

In this extreme case, the number of ascending intervals is never going to be larger than `len(prices)/2`. So is the number of transactions needed to capture all ascending intervals.

For more smooth cases, you don’t need `len(prices)/2` that many transactions to get all ascending intervals. However, we can use the same piece of codes to deal with any cases, as long as `k >= len(prices)/2`.  (line 10 – 15)

Now let’s look at the core part. I use a 2D array `profit` to capture the temporary maximum profit I can get: `profit[i][j]` is the maximum profit you can get by using `i` transactions and the first `j` prices. There is also a variable `tmp`. Its value is the maximum money left in the pocket after you buy the stock but haven’t sold it before you process `profit[i][j]`.  You can imagine `tmp` as the current best buy point.

Reference

https://leetcode.com/discuss/25603/a-concise-dp-solution-in-java