当前位置：首页 > news >正文

牛客NC403 编辑距离为一【中等模拟法 Java,Go,PHP】

news 2025/8/18 22:05:36

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/0b4b22ae020247ba8ac086674f1bd2bc

思路

	注意：必须要新增一个，或者删除一个，或者替换一个，所以不能相等1.如果s和t相等，返回false,如果s和t长度差大于1，返回false2.s比t长，s删除【忽略】一个，比较是否相等3.s比t短，t要删除【忽略】一个，比较是否相等4.s和t一样长，那么找到第一个不同的字符的位置，过滤掉。比较后面的是否相等

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param t string字符串* @return bool布尔型*/public boolean editdistance (String s, String t) {int n = s.length();int m = t.length();int diff = Math.abs(n - m);if (s.equals(t) || diff > 1  ) return false;int i = 0, j = 0;while (i < n && j < m && s.charAt(i) == t.charAt(j)) {i++;j++;}if (n > m) { //s比t多一个，那s就删一个return s.substring(i + 1).equals(t.substring(j));} else if (n < m) { //s比t少一个，那就s加一个return s.substring(i).equals(t.substring(j + 1));} else { //相等，那就替换,s和t都往前走一步return s.substring(i + 1).equals(t.substring(j + 1));}}
}

参考答案Go

package main//import "fmt"/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param t string字符串* @return bool布尔型*/
func editdistance(s string, t string) bool {n := len(s)m := len(t)diff := m - nif n > m {diff = n - m}if s == t || diff > 1 {return false}i := 0j := 0for i < n && j < m && s[i] == t[j] {i++j++}if n > m { //s 比t多一个，s删一个return s[i+1:] == t[j:]} else if n < m { //s比t少一个，s就加一个return s[i:] == t[j+1:]} else { //s和t一样长，那就替换，也就是s和t都往前走一步return s[i+1:] == t[j+1:]}
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param s string字符串 * @param t string字符串 * @return bool布尔型*/
function editdistance( $s ,  $t )
{$n = strlen($s);$m = strlen($t);$diff  = $n-$m;if($m>$n) {$diff = $m-$n;}if($s==$t || $diff >1) return false;$i=0;$j=0;while ($i<$n&& $j<$m && $s[$i]==$t[$j]){$i++;$j++;}if($n > $m){ //s多一个，删s中的那个return substr($s,$i+1) == substr($t,$j);}else if($n < $m){ //s少一个，s中加一个return substr($s,$i) == substr($t,$j+1);}else{ //s,t长度一样，替换，都往前走一步return substr($s,$i+1) == substr($t,$j+1);}
}