ストリング

LeetCode 161. 1つの編集距離--Python、Java、C ++ソリューション



Leetcode 161 One Edit Distance Python



LeetCodeタイトル列： LeetCodeソリューション
私が行ったすべてのLeetCodeトピックはこの列にあり、そのほとんどにJavaおよびPythonソリューションがあります。
私のコラムをフォローする皆さんを歓迎します。

この質問へのリンク： 1つの編集距離-LeetCode
このトピックの高度なバージョン 距離の編集-LeetCode
記事のアドレス： LeetCode72。距離の編集-zhangpeterxのブログ-CSDNブログ



2つの文字列sとtが与えられた場合、それらが両方とも1つの編集距離だけ離れているかどうかを判別します。

注意：



1つの編集距離を満足させるには、次の3つの可能性があります。

  • sに文字を挿入してtを取得します
  • sから文字を削除してtを取得します
  • sの文字を置き換えてtを取得します
    例1：
Input: s = 'ab', t = 'acb' Output: true Explanation: We can insert 'c' into s to get t.

例2：

Input: s = 'cab', t = 'ad' Output: false Explanation: We cannot get t from s by only one step.

例3：



Input: s = '1203', t = '1213' Output: true Explanation: We can replace '0' with '1' to get t.

sとtが1つの編集距離である場合、sとtの長さが等しいか、置換を行うか、長さの差が1であるか、削除または挿入します。
Pythonソリューションは次のとおりです。

class Solution: def isOneEditDistance(self, s: str, t: str) -> bool: lenS=len(s) lenT=len(t) if lenS>lenT: s,t=t,s lenS,lenT=lenT,lenS if lenS==lenT: count=0 for i in range(0,lenS): if s[i]!=t[i]: count+=1 if count>=2: break if count==1: return True else: return False elif lenT-lenS>=2: return False else: flag=0 for i in range(0,lenT): if i==lenT-1 and flag==0: return True elif s[i-flag]!=t[i]: if flag==0: flag=1 else: return False return True

Javaソリューションは次のとおりです。

class Solution { public boolean isOneEditDistance(String s, String t) { int ns = s.length() int nt = t.length() // Ensure that s is shorter than t. if (ns > nt) return isOneEditDistance(t, s) // The strings are NOT one edit away distance // if the length diff is more than 1. if (nt - ns > 1) return false for (int i = 0 i < ns i++) if (s.charAt(i) != t.charAt(i)) // if strings have the same length if (ns == nt) return s.substring(i + 1).equals(t.substring(i + 1)) // if strings have different lengths else return s.substring(i).equals(t.substring(i + 1)) // If there is no diffs on ns distance // the strings are one edit away only if // t has one more character. return (ns + 1 == nt) } }

C ++ソリューションは次のとおりです。

class Solution { public: bool isOneEditDistance(string s, string t) { int m = s.size(), n = t.size() if (m > n) { return isOneEditDistance(t, s) } for (int i = 0 i < m i++) { if (s[i] != t[i]) { if (m == n) { return s.substr(i + 1) == t.substr(i + 1) } return s.substr(i) == t.substr(i + 1) } } return m + 1 == n } }