两个字符串之间的编辑是以下更改之一。
null
- 添加一个角色
- 删除字符
- 换个角色
给定两个字符串s1和s2，找出s1是否可以通过一次编辑转换为s2。预期的时间复杂度为O（m+n），其中m和n是两个字符串的长度。 例如：
Input: s1 = "geeks", s2 = "geek"Output: yesNumber of edits is 1Input: s1 = "geeks", s2 = "geeks"Output: noNumber of edits is 0Input: s1 = "geaks", s2 = "geeks"Output: yesNumber of edits is 1Input: s1 = "peaks", s2 = "geeks"Output: noNumber of edits is 2
A. 简单解决方案 就是找到 使用动态规划编辑距离 .如果距离为1，则返回true，否则返回false。该解的时间复杂度为O（n） 2. ) 一 有效解决方案 是同时遍历两个字符串并跟踪不同字符的计数。下面是完整的算法。
Let the input strings be s1 and s2 and lengths of input strings be m and n respectively.1) If difference between m an n is more than 1, return false.2) Initialize count of edits as 0.3) Start traversing both strings from first character. a) If current characters don't match, then (i) Increment count of edits (ii) If count becomes more than 1, return false (iii) If length of one string is more, then only possible edit is to remove a character. Therefore, move ahead in larger string. (iv) If length is same, then only possible edit is to change a character. Therefore, move ahead in both strings. b) Else, move ahead in both strings.
以下是上述理念的实施情况：
C++
// C++ program to check if given two strings are // at distance one. #include <bits/stdc++.h> using namespace std; // Returns true if edit distance between s1 and // s2 is one, else false bool isEditDistanceOne(string s1, string s2) { // Find lengths of given strings int m = s1.length(), n = s2.length(); // If difference between lengths is more than // 1, then strings can't be at one distance if ( abs (m - n) > 1) return false ; int count = 0; // Count of edits int i = 0, j = 0; while (i < m && j < n) { // If current characters don't match if (s1[i] != s2[j]) { if (count == 1) return false ; // If length of one string is // more, then only possible edit // is to remove a character if (m > n) i++; else if (m< n) j++; else //Iflengths of both strings is same { i++; j++; } // Increment count of edits count++; } else // If current characters match { i++; j++; } } // If last character is extra in any string if (i < m || j < n) count++; return count == 1; } // Driver program int main() { string s1 = "gfg" ; string s2 = "gf" ; isEditDistanceOne(s1, s2)? cout << "Yes" : cout << "No" ; return 0; } |
JAVA
// Java program to check if given // two strings are at distance one. class GFG { // Returns true if edit distance // between s1 and s2 is one, else false static boolean isEditDistanceOne(String s1, String s2) { // Find lengths of given strings int m = s1.length(), n = s2.length(); // If difference between lengths is // more than 1, then strings can't // be at one distance if (Math.abs(m - n) > 1 ) return false ; int count = 0 ; // Count of edits int i = 0 , j = 0 ; while (i < m && j < n) { // If current characters don't match if (s1.charAt(i) != s2.charAt(j)) { if (count == 1 ) return false ; // If length of one string is // more, then only possible edit // is to remove a character if (m > n) i++; else if (m< n) j++; else // Iflengths of both strings // is same { i++; j++; } // Increment count of edits count++; } else // If current characters match { i++; j++; } } // If last character is extra // in any string if (i < m || j < n) count++; return count == 1 ; } // driver code public static void main (String[] args) { String s1 = "gfg" ; String s2 = "gf" ; if (isEditDistanceOne(s1, s2)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to check if given two strings are # at distance one # Returns true if edit distance between s1 and s2 is # one, else false def isEditDistanceOne(s1, s2): # Find lengths of given strings m = len (s1) n = len (s2) # If difference between lengths is more than 1, # then strings can't be at one distance if abs (m - n) > 1 : return false count = 0 # Count of isEditDistanceOne i = 0 j = 0 while i < m and j < n: # If current characters dont match if s1[i] ! = s2[j]: if count = = 1 : return false # If length of one string is # more, then only possible edit # is to remove a character if m > n: i + = 1 elif m < n: j + = 1 else : # If lengths of both strings is same i + = 1 j + = 1 # Increment count of edits count + = 1 else : # if current characters match i + = 1 j + = 1 # if last character is extra in any string if i < m or j < n: count + = 1 return count = = 1 # Driver program s1 = "gfg" s2 = "gf" if isEditDistanceOne(s1, s2): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Bhavya Jain |
C#
// C# program to check if given // two strings are at distance one. using System; class GFG { // Returns true if edit distance // between s1 and s2 is one, else false static bool isEditDistanceOne(String s1, String s2) { // Find lengths of given strings int m = s1.Length, n = s2.Length; // If difference between lengths is // more than 1, then strings can't // be at one distance if (Math.Abs(m - n) > 1) return false ; // Count of edits int count = 0; int i = 0, j = 0; while (i < m && j < n) { // If current characters // don't match if (s1[i] != s2[j]) { if (count == 1) return false ; // If length of one string is // more, then only possible edit // is to remove a character if (m > n) i++; else if (m< n) j++; // If lengths of both // strings is same else { i++; j++; } // Increment count of edits count++; } // If current characters match else { i++; j++; } } // If last character is extra // in any string if (i < m || j < n) count++; return count == 1; } // Driver code public static void Main () { String s1 = "gfg" ; String s2 = "gf" ; if (isEditDistanceOne(s1, s2)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to check if given // two strings are at distance one. // Returns true if edit distance // between s1 and s2 is one, else // false function isEditDistanceOne( $s1 , $s2 ) { // Find lengths of given strings $m = strlen ( $s1 ); $n = strlen ( $s2 ); // If difference between // lengths is more than // 1, then strings can't // be at one distance if ( abs ( $m - $n ) > 1) return false; // Count of edits $count = 0; $i = 0; $j = 0; while ( $i < $m && $j < $n ) { // If current characters // don't match if ( $s1 [ $i ] != $s2 [ $j ]) { if ( $count == 1) return false; // If length of one string is // more, then only possible edit // is to remove a character if ( $m > $n ) $i ++; else if ( $m < $n ) $j ++; // If lengths of both // strings is same else { $i ++; $j ++; } // Increment count of edits $count ++; } // If current characters // match else { $i ++; $j ++; } } // If last character is // extra in any string if ( $i < $m || $j < $n ) $count ++; return $count == 1; } // Driver Code $s1 = "gfg" ; $s2 = "gf" ; if (isEditDistanceOne( $s1 , $s2 )) echo "Yes" ; else echo "No" ; // This code is contributed by nitin mittal. ?> |
Javascript
<script> // Javascript program to check if given // two strings are at distance one. // Returns true if edit distance // between s1 and s2 is one, else false function isEditDistanceOne(s1, s2) { // Find lengths of given strings let m = s1.length, n = s2.length; // If difference between lengths is // more than 1, then strings can't // be at one distance if (Math.abs(m - n) > 1) return false ; // Count of edits let count = 0; let i = 0, j = 0; while (i < m && j < n) { // If current characters // don't match if (s1[i] != s2[j]) { if (count == 1) return false ; // If length of one string is // more, then only possible edit // is to remove a character if (m > n) i++; else if (m< n) j++; // If lengths of both // strings is same else { i++; j++; } // Increment count of edits count++; } // If current characters match else { i++; j++; } } // If last character is extra // in any string if (i < m || j < n) count++; return count == 1; } let s1 = "gfg" ; let s2 = "gf" ; if (isEditDistanceOne(s1, s2)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by decode2207. </script> |
输出：
Yes
时间复杂度：O（n） 辅助空间：O（1） 感谢Gaurav Ahirwar提出上述解决方案。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
