边工作边刷题：70天一遍leetcode: day 75-1

Shortest Word Distance I/II/III

要点：系列题最重要的是记清题，重点是题目本身的变化和解法之间的关联。

I https://repl.it/CqPf

• 这题的一般规律从左到右的某个word提供了boundary为之后的word做比较用：所以遇到两个word中的一个，一是和另一个word比较，二是更新本word的boundary。
• 和Closest Binary Search Tree Value很像，都是boundary限定

III https://repl.it/CqSA

• I里面两个word不同，遇到任意一个和另一个是互斥的。所以III扩展为可能相同的情况，而word1==word2意义就变了：变成了两个word在不同位置的距离，如果还按1的方法，永远不能比较另一个word。
• 简单的方法就是在处理第一个word的时候多检查word1word2，这时候和idx1本身算距离, 如果word1word2，就不会落到elif的branch

II https://repl.it/CqPa

• 用map记录index，题目就转化成了类似merge的算法了。

# Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

# For example,

# Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

# Given word1 = “coding”, word2 = “practice”, return 3.

# Given word1 = "makes", word2 = "coding", return 1.

# Note:

# You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

# Hide Company Tags LinkedIn

# Hide Tags Array

# Hide Similar Problems (M) Shortest Word Distance II (M) Shortest Word Distance III

class Solution(object):

    def shortestDistance(self, words, word1, word2):

        """

        :type words: List[str]

        :type word1: str

        :type word2: str

        :rtype: int

        """

        p1, p2 = -1, -1

        shortest = len(words)

        for i in xrange(len(words)):

            if words[i]==word1:

                if p2!=-1 and shortest > i-p2:

                    shortest = i-p2

                p1 = i

            elif words[i]==word2:

                if p1!=-1 and shortest > i-p1:

                    shortest = i-p1

                p2 = i

        return shortest

# This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.

# Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

# word1 and word2 may be the same and they represent two individual words in the list.

# For example,

# Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

# Given word1 = “makes”, word2 = “coding”, return 1.

# Given word1 = "makes", word2 = "makes", return 3.

# Note:

# You may assume word1 and word2 are both in the list.

# Hide Company Tags LinkedIn

# Hide Tags Array

# Hide Similar Problems (E) Shortest Word Distance (M) Shortest Word Distance II

class Solution(object):

    def shortestWordDistance(self, words, word1, word2):

        """

        :type words: List[str]

        :type word1: str

        :type word2: str

        :rtype: int

        """

        p1, p2 = -1, -1

        shortest = len(words)

        for i in xrange(len(words)):

            if words[i]==word1:

                if word1==word2 and p1!=-1:

                    shortest = min(shortest, i-p1)

                elif p2!=-1:

                    shortest = min(shortest, i-p2)

                p1 = i

            elif words[i]==word2:

                if p1!=-1:

                    shortest = min(shortest, i-p1)

                p2 = i

        return shortest

# This is a follow up of Shortest Word Distance. The only difference is now you are given the list of words and your method will be called repeatedly many times with different parameters. How would you optimize it?

# Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list.

# For example,

# Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

# Given word1 = “coding”, word2 = “practice”, return 3.

# Given word1 = "makes", word2 = "coding", return 1.

# Note:

# You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

# Hide Company Tags LinkedIn

# Hide Tags Hash Table Design

# Hide Similar Problems (E) Merge Two Sorted Lists (E) Shortest Word Distance (M) Shortest Word Distance III

from collections import defaultdict

class WordDistance(object):

    def __init__(self, words):

        """

        initialize your data structure here.

        :type words: List[str]

        """

        self.wordpos = defaultdict(list)

        [self.wordpos[words[i]].append(i) for i in xrange(len(words))]

    def shortest(self, word1, word2):

        """

        Adds a word into the data structure.

        :type word1: str

        :type word2: str

        :rtype: int

        """

        wl1 = self.wordpos[word1]

        wl2 = self.wordpos[word2]

        i,j = 0,0

        shortest = sys.maxint

        while i<len(wl1) and j<len(wl2):

            shortest = min(shortest, abs(wl1[i]-wl2[j]))

            if wl1[i]<wl2[j]:

                i+=1

            else:

                j+=1

        return shortest

# Your WordDistance object will be instantiated and called as such:

# wordDistance = WordDistance(words)

# wordDistance.shortest("word1", "word2")

# wordDistance.shortest("anotherWord1", "anotherWord2")