72. Edit Distance

https://leetcode.com/problems/edit-distance/

Edit Distance - LeetCode

방향에 의미 부여하기

 

328 ms

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if len(word1) == 0 or len(word2) == 0:
            return max(len(word1), len(word2))
        
        dp = []
        for i in range(len(word1)+1):
            if i == 0:
                dp.append(list(range(len(word2)+1)))
                continue
            dp.append([i]+[float('inf')]*(len(word2)))
        
        for _i, a in enumerate(word1):
            i = _i+1
            for _j, b in enumerate(word2):
                j = _j+1
                dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
                dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
                if a == b:
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1])
                else:
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1)
        
        return dp[len(word1)][len(word2)]

 

dp 2차원 배열을 선언하지 않고, queue를 이용해 특이하게 풀었다.

이해해보자.

 

52ms

class Solution:
  def minDistance(self, word1: str, word2: str) -> int:
      l1,l2 = len(word1),len(word2)
      visited = set()
      q = deque([(0, 0, 0)])
        
      while q:
        p1, p2, dist = q.popleft()
        if (p1, p2) not in visited and p1<=l1 and p2<=l2:
          visited.add((p1, p2))
          
          if word1[p1:] == word2[p2:]:
            return dist

          while p1<l1 and p2<l2 and word1[p1] == word2[p2]:
            p1 += 1
            p2 += 1

          dist += 1
          q.extend([(p1+1, p2+1, dist), (p1, p2+1, dist), (p1+1, p2, dist)])