给定两个字符串 s 和 t ,如果两个字符串的编辑距离是 1 则输出 true 否则输出 false。
字符串 s 和字符串 t 的编辑距离是 1 时有三种情形。
从 s 中删除一个字符得到 t
往 s 中添加一个字符得到 t
在 s 中修改任意一个字符得到 t
数据范围:两个字符串的长度满足 ,字符串中仅包含小写英文字母
"nowcoder","nawcoder"
true
"nowcoder","nawcader"
false
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @param t string字符串 * @return bool布尔型 */ bool editdistance(string s, string t) { // write code here if(s.length() == t.length() + 1){ for(int i=0; i<t.length(); i++){ if(s[i] != t[i]){ s.erase(s.begin()+i); return s == t; } } return true; } if(s.length() == t.length() - 1){ for(int i=0; i<s.length(); i++){ if(s[i] != t[i]){ t.erase(t.begin()+i); return s == t; } } return true; } if(s.length() == t.length()){ if(s == t){ return false; } for(int i=0; i<s.length(); i++){ if(s[i] != t[i]){ s[i] = t[i]; return s == t; } } } return false; } };
import java.util.*; public class Solution { public boolean editdistance (String s, String t) { int lenS = s.length(); int lenT = t.length(); int dif = Math.abs(lenS - lenT); if (dif > 1) { return false; } if (lenS > lenT) { return editdistance(t, s); } // lenS <= lenT for (int i = 0; i < s.length(); i++) { // 如果两个字符不等 if (s.charAt(i) != t.charAt(i)) { // 如果长度不等 if (dif == 1) { return s.substring(i).equals(t.substring(i + 1)); } else { return s.substring(i + 1).equals(t.substring(i + 1)); } } } return dif == 1; } }
bool editdistance(string s, string t) { // write code here int lens=s.size(); int lent=t.size(); if(abs(lens-lent)>1) { return false; } if(lens==lent)//长度相同,只能修改一个字符 { int cnt=0; for(int i=0;i<lens;i++) { if(s[i]!=t[i]) { cnt++; } if(cnt>1) { return false; } } if(cnt==0)//完全相等,编辑距离为0 { return false; } } else //长度短的添加一个字符 { if(lens<lent) { int cnt=0; for(int i=0;i<lens;i++) { if(cnt==0) { if(s[i]!=t[i]) { cnt++; i--; } } else { if(s[i]!=t[i+1]) { return false; } } } } else { int cnt=0; for(int i=0;i<lent;i++) { if(cnt==0) { if(s[i]!=t[i]) { cnt++; i--; } } else { if(s[i+1]!=t[i]) { return false; } } } } } return true; }