0583.go

// Source: https://leetcode.com/problems/delete-operation-for-two-strings
// Title: Delete Operation for Two Strings
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
//
// In one step, you can delete exactly one character in either string.
//
// Example 1:
//
//   Input: word1 = "sea", word2 = "eat"
//   Output: 2
//   Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
//
// Example 2:
//
//   Input: word1 = "leetcode", word2 = "etco"
//   Output: 4
//
// Constraints:
//
//   1 <= word1.length, word2.length <= 500
//   word1 and word2 consist of only lowercase English letters.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package main

func minDistance(word1 string, word2 string) int {
	l1 := len(word1)

	dist := make([]int, l1+1)

	for i := 0; i <= l1; i++ {
		dist[i] = i
	}

	for j, c2 := range word2 {
		tmp := dist[0]
		dist[0] = j + 1
		for i, c1 := range word1 {
			next := _min(dist[i], dist[i+1]) + 1
			if c1 == c2 {
				next = _min(next, tmp)
			}
			tmp = dist[i+1]
			dist[i+1] = next
		}
	}

	return dist[l1]
}

func _min(a, b int) int {
	if a < b {
		return a
	}
	return b
}