#32174 (Go) No.225 文字列変更(medium)

• 問題: No.225 文字列変更(medium)
• ユーザー: fmhr
• 提出日時: 2015-06-12 23:03:43
• 言語: Go (1.22.1)
• 結果: AC
• 実行時間: 16 ms / 5,000 ms
• コード長: 879 bytes
• コンパイル時間: 10,040 ms
• コンパイル使用メモリ: 203,608 KB
• 実行使用メモリ: 12,272 KB
• 最終ジャッジ日時: 2023-08-25 22:44:48
• 合計ジャッジ時間: 11,100 ms
• ジャッジサーバーID （参考情報）: judge12 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	7 ms; 5,692 KB
testcase_01	AC	10 ms; 7,968 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	1 ms; 4,380 KB
testcase_05	AC	1 ms; 4,376 KB
testcase_06	AC	1 ms; 4,380 KB
testcase_07	AC	1 ms; 4,376 KB
testcase_08	AC	1 ms; 4,376 KB
testcase_09	AC	1 ms; 4,380 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	1 ms; 4,380 KB
testcase_12	AC	15 ms; 10,144 KB
testcase_13	AC	15 ms; 12,272 KB
testcase_14	AC	15 ms; 12,220 KB
testcase_15	AC	16 ms; 10,144 KB
testcase_16	AC	13 ms; 12,220 KB
testcase_17	AC	15 ms; 10,144 KB
testcase_18	AC	14 ms; 10,140 KB
testcase_19	AC	13 ms; 10,156 KB
testcase_20	AC	13 ms; 10,136 KB
testcase_21	AC	13 ms; 10,152 KB

ソースコード

package main

import (
	"fmt"
	"strings"
)

func main() {
	var n, m int
	var S, T string
	fmt.Scan(&n, &m, &S, &T)
	s:= strings.Split(S,"")
	t:= strings.Split(T,"")
	fmt.Println(lesvenshteinDistance(s, t))
}

func lesvenshteinDistance(str1 []string, str2 []string)int{
	d := makeDoubleSliceInt(len(str1)+1, len(str2)+1)
	for i1 :=0; i1<=len(str1);i1++{
		d[i1][0]=i1
	}
	for i2:=0; i2<=len(str2);i2++{
		d[0][i2] = i2
	}
	var cost int
	for i:=1;i<len(str1)+1;i++{
		for j:=1;j<len(str2)+1;j++{
			if str1[i-1]==str2[j-1]{
				cost=0
			}else{
				cost=1
			}
			d[i][j]=min(d[i-1][j]+1, min(d[i][j-1]+1, d[i-1][j-1]+cost))
		}
	}
	//fmt.Println(d)
	return d[len(str1)][len(str2)]
}

func makeDoubleSliceInt(y, x int) [][]int {
	ss := make([][]int, y)
	for i := range ss {
		ss[i] = make([]int, x)
	}
	return ss
}

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