Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
// lengths are same => then only one char mismatch is allowed and both strs move forward
// lengths differ by 1 => only one mismatch is allowed and str of bigger length move forward
// lengths biffer by > 1 => return false;
bool oneEdit(string str1,string str2)
{
bool oneless= false, same = false;
bool oneditAlready = false;
int diff = str1.length() - str2.length() ;
if( abs(diff) > 1 )
return false;
if( abs(diff) == 0 )
same = true;
else
oneless = true;
for(unsigned int i=0, j=0; i<str1.length() && j<str2.length();)
{
if(str1[i]==str2[j])
{
i++;j++;continue;
}
if(oneditAlready)
return false;
oneditAlready = true;
if(oneless) // which one to plus
{
if(str1.length() > str2.length())
i++;
else
j++;
}
if(same) // both move forward
{
i++;j++;
}
}
if(oneless) // if there is oneless and oneditAlready is not true then it is fine
return true;
if(same && !oneditAlready)
return false;
}
int main()
{
cout << oneEdit("xyzkqow","xyzmqow") << endl;
cout << oneEdit("abcd", "abc") << endl;
cout << oneEdit("xyz", "xz") << endl;
cout << oneEdit("xyz", "xyk") << endl;
cout << oneEdit("xy", "xyz") << endl;
cout << oneEdit("xyz", "xyz") << endl;
cout << oneEdit("xyz","xzy") << endl;
cout << oneEdit("x", "xyz") << endl;
return 0;
}
Observation:
1) There could be at most one character differ from both Strings.
2) When the strings lengths are equal, the solution is straight forward: advance both charAt pointers at the same time until the the difference is found.
3) When the strings lengths are not equal, off by one we will need to stall pointer of the shorter string when the first difference is found. And after that it should behave like (2).
And the code should look like:
// Java
boolean findSingleCharacterDifference(String left, String right) {
String longer = left.length() > right.length() ? left : right;
String shorter = left.length() > right.length() ? right : left;
boolean stalled = left.length() == right.length();
for (int i = 0; i < shorter.length(); i++) {
if (shorter.charAt(i) != longer.charAt(i)) {
// When we have encountered our first difference, the remaining substring
// must be equal to be true.
int offset = stalled ? 1 : 0;
return shorter.substring(i + 1).equals(longer.substring(i + 1+ offset));
}
}
// Assert left.equals(right), we can choose to add if check at the beginning.
return false;
}
One more thing: your code will return false for "abcd","abc" (only last character deleted). Submitted an answer based on yours with some fixes
This is a modified version of Garukun's answer. Only with few fixes
public static boolean onlyOneEdit(String first, String second)
{
if(first.equals(second))
{
return false;
}
int l1 = first.length();
int l2 = second.length();
if(l1 - l2 > 1 || l2 - l1 > 1)
{
// At least two edits .. no need to continue
return false;
}
String longer = (l1 > l2)? first : second;
String shorter = (l1 > l2)? second : first;
for(int i = 0; i < shorter.length(); i++)
{
if(longer.charAt(i) != shorter.charAt(i))
{
int shift = (l1 == l2)? 0 : 1;
return longer.substring(i + 1 + shift).equals(shorter.substring(i + 1));
}
}
// No difference detected until the end of the shorter string
return true;
}
Your first check "if(first.equals(second))" is unnecessary, because what the .equals method does is it compares the chars in each string one by one, so it increased the time complexity.
O(n) solution:
#include <stdio.h>
#include <string.h>
bool single_edit(char *str1, char *str2)
{
while(*str1 && *str2) {
if(*str1 != *str2) break;
++str1; ++str2;
}
if(*str1 == '\0' && *str2 == '\0') return true;
return (strcmp(str1, str2 + 1) == 0 || strcmp(str1 + 1, str2) == 0 || strcmp(str1 + 1, str2 + 1) == 0);
}
int main(int argc, char *argv[])
{
char *str1 = argv[1];
char *str2 = argv[2];
printf("%d", single_edit(str1, str2));
return 0;
}
Note that this algorithm is using the fact that if one edit is made, the remaining string should be same.
#include <cstring>
#include <cassert>
using namespace std;
bool one_edit_apart(const char* s, const char* t) {
auto n = strlen(s), m = strlen(t);
m > n ? swap(n, m), swap(s, t), 0 : 0;
while (*t)
if (*s++ != *t++)
return n == m ? strcmp(s, t) == 0 : strcmp(s, t-1) == 0;
return n - m == 1; // to check a case such as "xyz" and "xy"
};
int main() {
assert(one_edit_apart("xyz", "xz"));
assert(one_edit_apart("xz", "xyz"));
assert(one_edit_apart("xyz", "xaz"));
assert(!one_edit_apart("abc", "abc"));
assert(!one_edit_apart("abc", "acb"));
assert(!one_edit_apart("ab", "abcd"));
return 0;
}
I like the C++11 implementation but I didn't like the recursion, it is too expensive on big strings.
Yes, you're right. Here is the non-recursive version and not checking 3 times.
auto one_edit_apart = [](const string& s, const string& t) {
auto n = s.length(), m = t.length();
auto is_same_str = [&](size_t i, size_t j) {
while (i < n && j < m) {
if (s[i++] != t[j++]) {
return false;
}
}
return i >= n && j >= m ? true : false;
};
for (size_t i = 0, j = 0; i < n && j < m; ++i, ++j) {
if (s[i] != t[j]) {
if (n == m)
return is_same_str(i+1,j+1); // replace
else if (n < m)
return is_same_str(i,j+1); // insertion
else
return is_same_str(i+1,j); // deletion
}
}
return labs(n-m) == 1; // to check cases such as "xy" and "xyz" or "ab" and "abcd" or "abc" and "abc"
};
Those OR expressions were fine because they work like as an 'if else' statement. The first true ends the evaluation.
Even if they work like as 'if else', is_same_str() can be 3 times called in the worst case. But the new code will call is_same_str() exactly once which I think is better. I thought you made a point in the previous comment.
O(n) implementation with no recursion or string length check.
#include <stdio.h>
#include <stdbool.h>
bool is_str_equal(char *str1, char *str2)
{
while (*str1 && *str2 && *str1 == *str2)
str1++,str2++;
return !(*str1 || *str2);
}
bool is_one_count(char *str1, char *str2)
{
while (*str1 && *str2 && *str1 == *str2)
str1++,str2++;
/* same string */
if (!(*str1 || *str2))
return false;
return is_str_equal(str1 + 1, str2) ||
is_str_equal(str1, str2 + 1) ||
is_str_equal(str1 + 1, str2 + 1) ||
is_str_equal(str1 - 1, str2) ||
is_str_equal(str1, str2 - 1);
}
int main(int argc, char *argv[])
{
printf("%s\n", (is_one_count("abbc","abcc")) ? "True" : "False");
return 0;
}
My solution: check characters from s1 and s2 until they're different, then skip 1 character in one or both strings based on the length of them, and check if the remains are identical:
#include <iostream>
#include <string>
using namespace std;
bool help(string s1, string s2, size_t p1, size_t p2)
{
for(size_t i = 0;p1 + i < s1.size();++i)
if(s1[p1 + i] != s2[p2 + i])
return false;
return true;
}
bool solve(string s1, string s2)
{
if(s1.size() > s2.size())
s1.swap(s2);
if(s1.size() + 1 < s2.size())
return false;
for(size_t i = 0;i < s1.size();++i){
if(s1[i] == s2[i])
continue;
if(s1.size() == s2.size())
return help(s1, s2, i + 1, i + 1);
return help(s1, s2, i, i + 1);
}
return (s1.size() < s2.size());
}
int main()
{
cout<<solve("xyz", "xz")<<endl;
cout<<solve("xyz", "xyk")<<endl;
cout<<solve("xy", "xyz")<<endl;
cout<<"---\n";
cout<<solve("xyz", "xyz")<<endl;
cout<<solve("xyz", "xzy")<<endl;
cout<<solve("xyz", "x")<<endl;
cout<<solve("x", "xyz")<<endl;
}
Here is a way to do it. I've included what I believe is a thorough set of unit test cases, and I've noticed some of the previously posted solutions don't handle them all correctly. If you have a solution to this, I encourage you to run it against all of the cases I've included below. Are there any test cases I missed?
One minor point that warrants a clarification question: None of the example cases show an insert growing the string to 4 characters. This leaves it ambiguous as to whether a change such as xyz --> axy can be considered a single edit (i.e. single insertion at beginning of a fixed 3-character buffer) or whether it is two edits (insertion of 'a' and deletion of 'z').
//
// main.cpp
// OffByOneEdit
//
// Created by Adam Smith on 11/27/14.
//
#include <iostream>
#include <string>
bool AreStringsOneEditDifferent(const std::string& str1, const std::string& str2)
{
unsigned long l1 = str1.length();
unsigned long l2 = str2.length();
// Exit early if length of strings differs by more than 1 character
// string.length() returns unsigned long, this is why absolute value function is not used.
if (((l1 > l2) && ((l1-l2) > 1))
|| ((l2>l1) && ((l2-l1) > 1))) return false;
// Special case for equal-length strings
if (l1 == l2)
{
bool bDiffFound = false; // Difference detected in equal-length strings
for (int i = 0; i < l1; ++i)
{
if (str1[i] != str2[i])
{
if (bDiffFound) return false;
bDiffFound = true;
}
}
return bDiffFound;
}
// Case for strings that differ in length by 1
int offset = 0;
const std::string &shorter = (l1 < l2) ? str1 : str2;
const std::string &longer = (l1 < l2) ? str2 : str1;
for (int i = 0; i < shorter.length(); ++i)
{
if (shorter[i] != longer[i+offset])
{
if (offset > 0) return false; // We found a second difference, fail.
offset = 1;
--i;
}
}
return true;
}
int main(int argc, const char * argv[])
{
std::cout << "Success Cases:" << std::endl;
//Single removal true test cases
std::cout << "xyz yz " << AreStringsOneEditDifferent("xyz", "yz") << std::endl;
std::cout << "xyz xz " << AreStringsOneEditDifferent("xyz", "xz") << std::endl;
std::cout << "xyz xy " << AreStringsOneEditDifferent("xyz", "xy") << std::endl;
//Single replacement with new character true test cases
std::cout << "xyz ayz " << AreStringsOneEditDifferent("xyz", "ayz") << std::endl;
std::cout << "xyz xaz " << AreStringsOneEditDifferent("xyz", "xaz") << std::endl;
std::cout << "xyz xya " << AreStringsOneEditDifferent("xyz", "xya") << std::endl;
//Single replacement with duplicate character true test cases
std::cout << "xyz yyz " << AreStringsOneEditDifferent("xyz", "yyz") << std::endl;
std::cout << "xyz zyz " << AreStringsOneEditDifferent("xyz", "zyz") << std::endl;
std::cout << "xyz xxz " << AreStringsOneEditDifferent("xyz", "xxz") << std::endl;
std::cout << "xyz xzz " << AreStringsOneEditDifferent("xyz", "xzz") << std::endl;
std::cout << "xyz xyx " << AreStringsOneEditDifferent("xyz", "xyx") << std::endl;
std::cout << "xyz xyy " << AreStringsOneEditDifferent("xyz", "xyy") << std::endl;
//Single insertion of new character true test cases
std::cout << "xyz axyz " << AreStringsOneEditDifferent("xyz", "axyz") << std::endl;
std::cout << "xyz xayz " << AreStringsOneEditDifferent("xyz", "xayz") << std::endl;
std::cout << "xyz xyaz " << AreStringsOneEditDifferent("xyz", "xyaz") << std::endl;
std::cout << "xyz xyza " << AreStringsOneEditDifferent("xyz", "xyza") << std::endl;
//Single insertion of duplicate true test cases
std::cout << "xyz xxyz " << AreStringsOneEditDifferent("xyz", "xxyz") << std::endl;
std::cout << "xyz xyyz " << AreStringsOneEditDifferent("xyz", "xyyz") << std::endl;
std::cout << "xyz xyzz " << AreStringsOneEditDifferent("xyz", "xyzz") << std::endl;
std::cout << std::endl << "Failure Cases:" << std::endl;
// Removal and replacement failure cases
std::cout << "xyz az " << AreStringsOneEditDifferent("xyz", "az") << std::endl;
std::cout << "xyz ya " << AreStringsOneEditDifferent("xyz", "ya") << std::endl;
std::cout << "xyz xa " << AreStringsOneEditDifferent("xyz", "xa") << std::endl;
std::cout << "xyz ay " << AreStringsOneEditDifferent("xyz", "ay") << std::endl;
// Removal and insert failure cases (that are not equivalent to one replace)
std::cout << "xyz yaz " << AreStringsOneEditDifferent("xyz", "yaz") << std::endl;
std::cout << "xyz yza " << AreStringsOneEditDifferent("xyz", "yza") << std::endl;
std::cout << "xyz axz " << AreStringsOneEditDifferent("xyz", "axz") << std::endl;
std::cout << "xyz xza " << AreStringsOneEditDifferent("xyz", "xza") << std::endl;
std::cout << "xyz axy " << AreStringsOneEditDifferent("xyz", "axy") << std::endl;
std::cout << "xyz xay " << AreStringsOneEditDifferent("xyz", "xay") << std::endl;
// Replace and insert failure cases
std::cout << "xyz aayz " << AreStringsOneEditDifferent("xyz", "aayz") << std::endl;
std::cout << "xyz ayaz " << AreStringsOneEditDifferent("xyz", "ayaz") << std::endl;
std::cout << "xyz ayza " << AreStringsOneEditDifferent("xyz", "ayza") << std::endl;
std::cout << "xyz axaz " << AreStringsOneEditDifferent("xyz", "axaz") << std::endl;
std::cout << "xyz xaaz " << AreStringsOneEditDifferent("xyz", "xaaz") << std::endl;
std::cout << "xyz xaza " << AreStringsOneEditDifferent("xyz", "xaza") << std::endl;
std::cout << "xyz axya " << AreStringsOneEditDifferent("xyz", "axya") << std::endl;
std::cout << "xyz xaya " << AreStringsOneEditDifferent("xyz", "xaya") << std::endl;
std::cout << "xyz xyaa " << AreStringsOneEditDifferent("xyz", "xyaa") << std::endl;
return 0;
}
static void Main(string[] args)
{
string string1 = "xyzkqow";
string string2 = "xyzbkqow";
Console.WriteLine("String1 is " + string1 + ", and 2 is " + string2);
int i1 = 0;
int i2 = 0;
int j1 = string1.Length - 1;
int j2 = string2.Length - 1;
int lengthDiff = Math.Abs(j1 - j2);
if (lengthDiff > 1)
{
Console.WriteLine("FAIL: String Lengths are too different");
return;
}
bool mismatch = false;
// search forward
while (i1 < string1.Length && i2 < string2.Length)
{
if (string1[i1] == string2[i2])
{
i1++;
i2++;
continue;
}
mismatch = true;
break;
}
if (!mismatch) {
if (string1.CompareTo(string2) == 0)
{
Console.WriteLine("FAIL: They are exactly the same");
return;
}
System.Console.WriteLine("PASS: They are off by one character at the end");
return;
}
mismatch = false;
//search backward up until the first mismatch we found
while (j1 != i1 && j2 != i2)
{
if(string1[j1] == string2[j2])
{
j1--;
j2--;
continue;
}
mismatch = true;
break;
}
if (!mismatch)
{
System.Console.WriteLine("PASS: Only one mismatch");
}
else
{
Console.WriteLine("FAIL: More than one mismatch");
}
}
will your code work for "xyzkq"; && xyzbiq"
i1= 3 and i2=3. then for next while loop it will compare only j1=4 and j2=5.
since they will be true u wont check further.
but ans here hsould be false
public class HelloWorld{
public static void main(String []args){
String s1="xyz";
String s2="xkk";
int len =s1.length();
int len1 =s2.length();
int diffLength=Math.abs(len-len1);
if(diffLength>1)
System.out.println("Cannot procced");
else
{
int max = Math.max(len,len1);
int min = Math.min(len,len1);
boolean dflag=true,iflag=true,uflag=true;
if(len-len1>0)
dflag = delete(s1,s2);
if(len-len1<0)
iflag = insert(s1,s2);
if(len-len1==0)
uflag = update(s1,s2);
if(dflag && iflag && uflag)
System.out.println("True");
else
System.out.println("False");
}
}
public static boolean delete(String s1,String s2){
boolean flag=true;
int diff=0;
char c1[]=s1.toCharArray();
char c2[]=s2.toCharArray();
int i =0, j=0;
while(i<c1.length && j<c2.length){
if(c1[i]==c2[j])
{
i++;
j++;
}
else{
diff++;
i++;
}
}
if(diff>=2)
{
flag=false;
// System.out.println("diff 2");
}
return flag;
}
public static boolean insert(String s1,String s2){
boolean flag=true;
int diff=0;
char c1[]=s1.toCharArray();
char c2[]=s2.toCharArray();
int i =0, j=0;
while(i<c1.length && j<c2.length){
if(c1[i]==c2[j])
{
i++;
j++;
}
else{
diff++;
j++;
}
}
if(diff>=2)
{
flag=false;
}
return flag;
}
public static boolean update(String s1,String s2){
boolean flag=true;
int diff=0;
char c1[]=s1.toCharArray();
char c2[]=s2.toCharArray();
int i =0, j=0;
while(i<c1.length && j<c2.length){
if(c1[i]==c2[j])
{
i++;
j++;
}
else{
diff++;
j++;
i++;
}
}
if(diff>=2)
{
flag=false;
}
return flag;
}
}
Get the length of the longest string (if s1 and s2 have different lengths). Find LCS between s1 and s2. Substract LCS length from the length of the longest string. If it is equal to 1 return true otherwise return false
def handle_removal(s1 , s2):
n = len(s1)
m = len(s2)
flag = False
i=0
j=0
while j<m:
if s1[i]!=s2[j]:
if flag:
return False
else:
flag = True
i += 1
else:
i += 1
j += 1
if i==n-1:
return not flag
return True
def handle_replacement(s1 , s2):
n = len(s1)
flag = False
i=0
while i<n:
if s1[i] != s2[i]:
if flag:
return False
else:
flag = True
i += 1
else:
i += 1
return flag
def one_edit_distance(s1 , s2):
n = len(s1)
m = len(s2)
if n==m+1:
return handle_removal(s1 , s2)
if n==m-1:
return handle_removal(s2 , s1)
if n==m:
return handle_replacement(s1 , s2)
return False
print "cat" , "dog",one_edit_distance("cat" , "dog")
print "cat" , "cats",one_edit_distance("cat" , "cats")
print "cat", "cut",one_edit_distance("cat", "cut")
print "cat", "cast",one_edit_distance("cat", "cast")
print "cat", "at",one_edit_distance("cat", "at")
print "cat", "acts",one_edit_distance("cat", "acts")
print "xyz" , "xz" ,one_edit_distance("xyz" , "xz")
print "xyz" , "xz" ,one_edit_distance("xyz" , "xz")
print "xyz" , "xyk" ,one_edit_distance("xyz" , "xyk")
print "xy" , "xyz" ,one_edit_distance("xy" , "xyz")
print "xyz" , "xyz" ,one_edit_distance("xyz" , "xyz")
print "xyz" , "xzy" ,one_edit_distance("xyz" , "xzy")
print "x" , "xyz" ,one_edit_distance("x" , "xyz")
bool oneEdit(string const &s1, string const &s2) {
if(s1.size() == s2.size()) {
int count = 0;
for(int i = 0; i < s1.size(); i++)
if(s1[i] != s2[i]) count++;
if(count == 1) return true;
return false;
}
else if(abs(s1.size() - s2.size()) == 1) {
string m, M;
if(s1.size() > s2.size()) m = s2, M = s1;
else m = s1, M = s2;
int edit = 0;
for(int i = 0, j = 0; i < m.size() && j < M.size(); ) {
if(m[i] != M[j]) {
j++;
edit++;
}
else {
j++, i++;
}
}
if(edit == 1) return true;
return false;
}
return false;
}
O(n)
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Main {
public static void main(String[] args){
List<String> strings = new ArrayList<String>();
strings.add("abc");
strings.add("abc");
strings.add("abc");
strings.add("abd");
strings.add("abc");
strings.add("ab");
strings.add("ab");
strings.add("abc");
strings.add("a");
strings.add("");
strings.add("");
strings.add("c");
strings.add("abde");
strings.add("abcde");
strings.add("bcdefg");
strings.add("abcdefg");
strings.add("");
strings.add("");
strings.add("abcdefg");
strings.add("abcdefg");
Iterator<String> iter = strings.iterator();
while(iter.hasNext()){
String a = (String) iter.next();
String b = (String) iter.next();
System.out.println(a + " - " + b + ": " + withinOneMutation(a, b));
}
}
public static boolean withinOneMutation(String str0, String str1){
int len0 = str0.length(), len1 = str1.length();
if(Math.abs(len0 - len1) > 1){
return false;
}
boolean mismatchFound = false;
int p0 = 0, p1 = 0;
while(p0 < len0 && p1 < len1){
if(str0.substring(p0, p0 + 1).equals(str1.substring(p1, p1 + 1))){
p0++;
p1++;
continue;
}
if(mismatchFound == true){
return false;
}
if(len0 > len1){
p0++;
}
else if(len1 > len0){
p1++;
}
else{
p0++;
p1++;
}
mismatchFound = true;
}
if(!mismatchFound){
return len0 == len1 ? false : true;
}
return true;
}
}
Not the optimal solution as it is O(n²).
public class Distance {
private static int minimum(int a, int b, int c) {
return Math.min(Math.min(a, b), c);
}
// from wikipedia
public static int computeLevenshteinDistance(String str1, String str2) {
int[][] distance = new int[str1.length() + 1][str2.length() + 1];
for (int i = 0; i <= str1.length(); i++)
distance[i][0] = i;
for (int j = 1; j <= str2.length(); j++)
distance[0][j] = j;
for (int i = 1; i <= str1.length(); i++)
for (int j = 1; j <= str2.length(); j++)
distance[i][j] = minimum(
distance[i - 1][j] + 1,
distance[i][j - 1] + 1,
distance[i - 1][j - 1] + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));
return distance[str1.length()][str2.length()];
}
public static boolean withinOneMutation(String str1, String str2) {
return computeLevenshteinDistance(str1, str2) == 1;
}
public static void main(String[] args) {
System.out.println(withinOneMutation("xyz", "xz")); // true
System.out.println(withinOneMutation("xyz", "xyk")); // true
System.out.println(withinOneMutation("xy", "xyz")); // true
System.out.println(withinOneMutation("xyz", "xyz")); // false
System.out.println(withinOneMutation("xyz", "xzy")); // false
System.out.println(withinOneMutation("w", "xyz")); // false
}
}
Here's my solution in C#.
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string s1 = "xyz";
string s2 = "xz";
bool result = check(s1, s2);
Console.WriteLine(result);
}
public static bool check(string s1, string s2)
{
//if they're the same, then we just return false
if (s1 == s2) return false;
//get the difference in length between the two
int lenDif = Math.Abs(s1.Length - s2.Length);
//length can only be at most one off
if (lenDif > 1) return false;
//if there's no dif in length, then it's an update
if (lenDif == 0)
{
bool swapped = false;
//go through chars
for (int i = 0; i < s1.Length; i++)
{
//if the chars don't match
if (s1[i] != s2[i])
{
//if we already did a swap,
//then two swaps means they're more than one edit apart
if (swapped) return false;
else swapped = true;
}
}
return true;
}
else //length is dif by 1 (insert/delete)
{
//which one is bigger?
//insert is the reverse of delete, so we can just check for delete
if (s1.Length > s2.Length) return checkDelete(s1, s2);
else return checkDelete(s2, s1);
}
}
private static bool checkDelete(string strLong, string strShort)
{
//create a "buffer" so we can compare permutations
char[] buffer = new char[strShort.Length];
for (int del = 0; del < strLong.Length; del++)
{
int writeIndex = 0;
for (int i = 0; i < strLong.Length; i++)
{
if (i == del) continue;
buffer[writeIndex] = strLong[i];
writeIndex++;
}
if (new String(buffer) == strShort) return true;
}
return false;
}
}
}
Find conditions to detect insert/delete and update.
#include <stdio.h>
bool detectOneEdit(const char *pa, const char *pb)
{
int modificationCount = 0;
if (!pa || !pb) return false;
while(true) {
if (*pa == '\0') {
while(*pb != '\0') {
// Insert
modificationCount++;
pb++;
}
break;
}
if (*pb == '\0') {
while(*pa != '\0') {
// Delete
modificationCount++;
pa++;
}
break;
}
if (*pa != *pb) {
if (*pa == *(pb + 1)) {
// Insert
modificationCount++;
pb++;
}
else if (*(pa + 1) == *pb) {
// Delete
modificationCount++;
pa++;
}
else {
// Update
modificationCount++;
pa++;
pb++;
}
}
else {
pa++;
pb++;
}
}
return (modificationCount == 1 ? true : false);
}
int main(void)
{
printf("%d : xyz, xz\n", detectOneEdit("xyz", "xz"));
printf("%d : xyz, xyk\n", detectOneEdit("xyz", "xyk"));
printf("%d : xy, xyz\n", detectOneEdit("xy", "xyz"));
printf("%d : xyz, xyz\n", detectOneEdit("xyz", "xyz"));
printf("%d : xyz, xzy\n", detectOneEdit("xyz", "xzy"));
printf("%d : x, xyz\n", detectOneEdit("x", "xyz"));
return 0;
}
Nice. I haven't tested it but I like the idea, that the strings must match within 1 character. You could make the loop while(modificationCount < 2) though, as the result is never true if modificationCount > 1.
Suggesting approach here which is easy to code
1. Get length of both the strings.
2. If length are same then, keep two pointers and traverse both the string, if characters match forward them, if characters dont match and its for very first time, move on. If you reach at the end, declare true if you find more than 1 mismatch return false for the 2nd mismatch.
3. If the length difference between two string is exactly 1(it means we can get either of the string by Insert/delete of one character), do the same but for the very fist mismatch, ignore the character in longer string and increment the longer string pointer and compare, if you reach at the end, return TRUE or for any further mismatch, return false.
public boolean checkEdits(String s1, String s2){
int numberOfEditsRequired= 0;
boolean isEditPossible = true;
int s1length = s1.length();
int s2length = s2.length();
int stringLengthDelta = Math.abs(s1length - s2length);
if (stringLengthDelta > 1 || s1 == s2){
isEditPossible = false;
}else{
String longerString = (s1length > s2length) ? s1 : s2;
String shorterString = (s1length > s2length) ? s2 : s1;
for(int index = 0; index < shorterString.length(); index++){
if (shorterString.charAt(index) != longerString.charAt(index)){
numberOfEditsRequired++;
if (numberOfEditsRequired > 1 ){
isEditPossible = false;
break;
}
}
}
if (numberOfEditsRequired >= 1 && s1length != s2length){
isEditPossible = false;
}
}
return isEditPossible;
}
private static boolean isOneEditDistanceApart(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
if(s1.equals(s2)) {
return false;
}
//Edit distance will be more than 1
if(Math.abs(len1-len2) > 1) {
return false;
}
String shorter = len1 > len2 ? s2:s1;
String longer = len1 > len2 ? s1:s2;
for(int i=0;i<shorter.length();i++) {
if(s1.charAt(i) != s2.charAt(i)) {
if(len1 == len2) {
return s1.substring(i+1).equals(s2.substring(i+1));
} else {
if(i == shorter.length()-1) {
//xyx and xz are not
return shorter.charAt(i) == longer.charAt(i+1);
} else {
//Else normal
return longer.substring(i+1).equals(shorter.substring(i+1));
}
}
}
}
return true;
}
import java.util.Scanner;
public class PatternChecking {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the first String :");
String str1 = scanner.nextLine();
System.out.println("Enter the second String :");
String str2 = scanner.nextLine();
if (checkForPattern(str1, str2)) {
System.out.println("The two strings are one edit apart");
} else {
System.out.println("The two strings are not one edit apart");
}
}
private static boolean checkForPattern(String str1, String str2) {
if (str1.equals(str2)) {
return false;
} else if (str1.length() - str2.length() > 1
|| str2.length() - str1.length() > 1) {
return false;
} else if (str1.length() - str2.length() <= 1
|| str2.length() - str1.length() <= 1) {
return evaluate(str1, str2);
}
return false;
}
private static boolean evaluate(String str1, String str2) {
int mismatch = 0;
int limit = 0;
int j = 0;
if (str1.length() <= str2.length()) {
limit = str1.length();
} else if (str2.length() <= str1.length()) {
limit = str2.length();
}
for (int i = 0; i <= limit - 1; i++) {
if (str1.charAt(i) != str2.charAt(j)) {
j = j - 1;
mismatch = mismatch + 1;
if (mismatch >= 2) {
return false;
}
}
j += 1;
}
return true;
}
}
private static boolean areOneEditApart(String s1, String s2) {
int m = s1.length();
int n = s2.length();
if(Math.abs(m-n) > 1) // if length of both the strings differs more than 1
return false;
if(s1.equals(s2)) // if they are exactly same. That means they are NOT ONE EDIT apart
return false;
int i=0;
int j=0;
while(i < m && j < n){
if(s1.charAt(i)==s2.charAt(j)){
i++;
j++;
continue;
}
if(s1.charAt(i)!=s2.charAt(j)){
if(s1.substring(i+1, m).equals(s2.substring(j, n)))
return true;
if(s1.substring(i, m).equals(s2.substring(j+1, n)))
return true;
}
}
return false;
}
private static boolean areOneEditApart(String s1, String s2) {
int m = s1.length();
int n = s2.length();
if(Math.abs(m-n) > 1) // if length of both the strings differs more than 1
return false;
if(s1.equals(s2)) // if they are exactly same. That means they are NOT ONE EDIT apart
return false;
int i=0;
int j=0;
while(i < m && j < n){
if(s1.charAt(i)==s2.charAt(j)){
i++;
j++;
continue;
}
if(s1.charAt(i)!=s2.charAt(j)){
if(s1.substring(i+1, m).equals(s2.substring(j, n)))
return true;
if(s1.substring(i, m).equals(s2.substring(j+1, n)))
return true;
}
}
return false;
}
One small modification in the above program is required inside the if case.
if(s1.charAt(i)!=s2.charAt(j)){
if(s1.substring(i+1, m).equals(s2.substring(j, n)))
return true;
else if(s1.substring(i, m).equals(s2.substring(j+1, n)))
return true;
else
break; // if it is not equal then break the loop and return false
}
#include<iostream>
using namespace std;
void checkIfOneDelete( string s1, string s2 ) {
unsigned i = 0;
for(; i < s2.size(); i++) {
if(s1[i] != s2[i])
break;
}
for(; i < s2.size(); i++) {
if(s1[i+1] != s2[i]) {
cout<<"False"<<endl;
return;
}
}
cout<<"True"<<endl;
}
int main() {
string s1,s2;
s1 = "xyz";
s2 = "xzy";
if(s1.size() == s2.size()) {
int numDiff = 0;
for(unsigned i = 0; i < s1.size(); i++) {
if(s1[i] != s2[i]) numDiff++;
}
if(numDiff == 1)
cout<<"True"<<endl;
else
cout<<"False"<<endl;
return 0;
}
else if(s1.size() == (s2.size() + 1)) {
checkIfOneDelete(s1,s2);
}
else if(s2.size() == (s1.size() + 1)) {
checkIfOneDelete(s2,s1);
}
else {
cout<<"False"<<endl;
}
}
Here's the easy-to-read, clean cut approach:
bool offByOneEdit(string s1, string s2)
{
switch (s1.length() - s2.length())
{
case 0: return offByUpdate(s1, s2);
case -1: return offByInsert(s1, s2);
case 1: return offByInsert(s2, s1);
default: return false;
}
}
bool offByUpdate(string s1, string s2)
{
short errors = 0;
for (int i = 0; i < s1.length(); ++i)
{
if (s1[i] != s2[i] && errors++)
return false;
}
return errors == 1; // A perfect match has 0 errors, there should be 1
}
bool offByInsert(string s1, string s2)
{
short offset = 0;
for (int i = 0; i < s1.length(); ++i)
{
if (s1[i] != s2[i+offset] && offset++)
return false;
}
return true; // We already checked the length, so we know it's off by 1
}
And here's the one where I get rid of the separate functions and jam everything together, just for fun:
bool offByOne(string s1, string s2)
{
int s1off = 0, s2off = 0, errors = 0, l1 = s1.length(), l2 = s2.length();
int slen = l1 < l2 ? l1 : l2;
if (abs(l1 - l2) > 1)
return false;
for (int i = 0; i < slen; ++i)
{
if (s1[i+s1off] != s2[i+s2off])
{
if (errors++ || s1off || s2off)
return false;
if (l1 < l2)
++s2off;
else if (l1 > l2)
++s1off;
}
}
return errors == 1 || (l1 != l2);
}
Pretty simple. Bail early if the difference in string length is more than 1. Definitely true if the length difference == 1. Otherwise apply a Hamming distance on the two strings
Time O(n)
Space O(1)
Ruby
def string_difference(a, b)
d = (a.length - b.length).abs
case d
when 0
x = 0
for i in 0..a.length
if a[i] != b[i] then x += 1 end
if x > 1 then return false end
end
return x == 1
when 1
return true
end
false
end
Based on Garukun's solution:
Conditions for TRUE:
1)length should match or should differ by 1
a) length matches: all characters except one should match. Both pointers should be moved after 1st difference is noticed
b) length differs by 1: all characters except one should match. Only pointer in bigger string should be moved when 1st difference is noticed.
import java.io.*;
import java.util.*;
/*
Conditions for TRUE:
1)length should match or should differ by 1
a) length matches: all characters except one should match. Both pointers should be moved after 1st difference is noticed
b) length differs by 1: all characters except one should match. Only pointer in bigger string should be moved when 1st difference is noticed.
*/
class Solution {
public static boolean singleEditMatch(String s1, String s2) {
if( Math.abs(s1.length() - s2.length()) > 1 ) {
return false;
}
boolean sameLength = s1.length() == s2.length();
String bigstring = s1.length() > s2.length()?s1:s2;
String smallstring = s2.length() > s1.length()?s2:s1;
int idx = 0;
boolean editCheck = true;
int mismatchCount = 0;
for(int i=0; i < bigstring.length(); i++) {
if(idx == smallstring.length()) {
idx--;
}
if(bigstring.charAt(i) == smallstring.charAt(idx)) {
idx++;
continue;
}
//mismatch
mismatchCount++;
if(mismatchCount > 1) {
//more mismatch, return false
editCheck = false;
break;
}
if(mismatchCount == 1 && !sameLength) {
// dont move index of smaller string for the first mismatch
} else {
// move index of smaller string in all other cases
idx++;
}
}
return editCheck;
}
public static void main(String[] args) {
//String str1="xyz", str2="xzy";
String str1="x", str2="xyz";
System.out.println(str1 + ":" + str2 + " --> " + singleEditMatch(str1,str2));
}
}
Here is the C++ solution using dynamic programming.
Running time is O(NM) where N is the length of the first string and M is for the second string.
#include <math.h>
#include <string>
#include <iostream>
using namespace std;
bool one_edit_apart(string src, string dst)
{
int w1 = src.length();
int w2 = dst.length();
int **w = new int*[w1+1];
for (int p = 0; p <= w1; p++)
w[p] = new int[w2+1];
for (int x = 0; x <= w1; x++)
w[x][0] = x;
for (int y = 0; y <= w2; y++)
w[0][y] = y;
for (int i = 1; i <= w1; i++)
{
for (int j = 1; j<= w2; j++)
{
int m = (src[i-1] != dst[j-1])+ w[i-1][j-1];
if ( m > min(1+ w[i-1][j], 1+ w[i][j-1]))
m = min(1+ w[i-1][j], 1+ w[i][j-1]);
w[i][j] = m;
}
}
cout<<"count = " << w[w1][w2]<<endl;
return (w[w1][w2] ==1);
}
int main()
{
cout << "xyz, xz: " << one_edit_apart("xyz", "xz") <<endl;
cout << "xyz, xyk: " << one_edit_apart("xyz", "xyk")<<endl;
cout << "xy, xyz: " << one_edit_apart("xy", "xyz")<<endl;
cout << "xyz, xyz: " << one_edit_apart("xyz", "xyz") <<endl;
cout << "xyz, xzy: " << one_edit_apart("xyz", "xzy")<<endl;
cout << "x, xyz: " << one_edit_apart("x", "xyz")<<endl;
return 1;
}
Here is faster and simpler solution running in O(N).
// O(N) solution
bool one_edit_apart(string src, string dst)
{
int w1 = src.length();
int w2 = dst.length();
if (src.length() > dst.length())
return one_edit_apart(dst, src);
if (src.length()+1 < dst.length())
return false;
for (int i = 0; i < src.length(); i++)
{
if (src[i] != dst[i])
{
if (src.length() == dst.length())
return (i <src.length()-1)? src[i+1] == dst[i+1] : true;
else
return src[i] == dst[i+1];
}
}
return (src.length()+1 == dst.length());
}
Edit Distance
function editDistance(str1, str2, m, n){
if(m == 0) return n;
if(n == 0) return m;
if(str1.charAt(m) == str2.charAt(n)) return editDistance(str1,str2, m-1, n-1);
return 1 + Math.min(
editDistance(str1,str2,m-1,n), // remove
editDistance(str1,str2,m,n-1), // insert
editDistance(str1,str2,m-1,n-1) // replace
);
}
var str1 = 'cat';
var str2 = 'at';
console.log('1 distance apart: ' + (editDistance(str1,str2,str1.length, str2.length) ==1));
#include <iostream>
#include <vector>
#include <set>
#include <utility>
using namespace std;
bool isTwoEdit(string s1, string s2){
set<char> set1(s1.begin(), s1.end());
set<char> set2(s2.begin(), s2.end());
int count=0;
for(set<char>::iterator it=set1.begin();it!=set1.end();it++){
set<char>::iterator it2 = set2.begin();
while(it2!=set2.end()){
if(*it == *it2){
count++;
}
it2++;
}
}
if(count==2){
return true;
}else{
return false;
}
}
int main(){
int n;
string s1, s2;
vector< pair<string,string> > v;
set<char> sol;
cin>>n;
for(int i=0;i<n;i++){
cin>>s1;
cin>>s2;
v.push_back(make_pair(s1,s2));
cout<<isTwoEdit(v[i].first, v[i].second)<<endl;
}
return 0;
}
Does this actually work? If I read the code correctly it seems to compare the first character of string 1 with each character of string 2, then character 2 of string 1 with each character of string 2, etc. So I believe therefore that if comparing "xxx" with "xxy" it would get to a count of 6 and return false, which is not correct. It works with the examples in the original problem, but doesn't work with duplicates. It also makes a big assumption that the strings are three characters long; for example, with the strings "x" and "xy" I think it would count 1 (and therefore false); "xy" and "xz" would count 1 and return false; "wxyz" and "xyz" would count 3 and return false.
public static boolean oneApart(String s1, String s2) {
for (int i = 0; i<s1.length() && i<s2.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
return (s1.substring(i).equals(s2.substring(i+1)) && (i+1) < s2.length())
|| (s1.substring(i+1).equals(s2.substring(i)) && (i+1) < s1.length())
|| (s1.substring(i).equals(s2.substring(i)))
|| ((i == (s1.length()-1)) && (i == (s2.length()-1)));
}
}
if (Math.abs(s1.length() - s2.length()) == 1) {
return true;
}
return false;
}
int edist1(const char *s1, const char *s2) {
/**
* Approach:
* Three cases:
* - first letter differs => every other one should be the same
* - first letter same => one at middle can differ or the last one
* - last letter differs => one string should not be two chars longer
* than the other
*/
int i, j;
int edited = 0;
i = j = 0;
if (s1[0] != s2[0]) {
if (s1[1] == s2[0]) i = 1; // s2 starts from second position of s1
else if (s1[0] == s2[1]) j = 1; // s1 starts from second position of s2
else return 0; // first two letters differ
}
edited = i + j;
for (;s1[i] != NULL && s2[j] != NULL; i++, j++) {
if (s1[i] != s2[j]) {
edited++;
if (edited==2) return 0;
}
}
if (s1[i] != NULL || s2[j] != NULL) {
if (edited) return 0;
if (s1[i] == NULL && s2[j+1] != NULL) return 0;
if (s2[j] == NULL && s1[i+1] != NULL) return 0;
}
return 1;
}
This code appears to fail to recognize any of the following as single-edits:
xyz xz //middle char removed
xyz ayz //first char replaced
xyz yyz //first char replaced
xyz zyz //first char replaced
xyz xayz // insertion at [1]
xyz xyaz // insertion at [2]
xyz xxyz // insertion of dupe at [1] or [2]
xyz xyyz // insertion at dupe [2] or [3]
- Wchuan91 November 06, 2014bool edit(string s1, string s2) { if(s2.size() < s1.size()) { return edit(s2, s1); } if(s1.size() + 1 < s2.size()) { return false; } int i = 0; while(i < s1.size()) { if(s1[i] != s2[i]) { if(s1.size() == s2.size()) { return s1.substr(i+1) == s2.substr(i+1); }else { return s1.substr(i) == s2.substr(i+1); } } i ++; } return s1.size() != s2.size(); }