Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
10
of 10 vote

bool 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();
}

- Wchuan91 November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}

- Garukun November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice simple solution, but the offset should be 1 when

left.length() != right.length()

- miro November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

One more thing: your code will return false for "abcd","abc" (only last character deleted). Submitted an answer based on yours with some fixes

- miro November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Miro, you're right, I missed the last TRUE case where xy and xyz are considered the same. That one along with the first one you mentioned are two easy edge cases, I'll update my code as well momentarily.

- Garukun November 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}

- miro November 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this fails for string1 as xyzkqow and string 2 as xyzbmqow

- king November 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zg911 November 15, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

doesn't work for string1 = abd and string2 = abcd

- holic87 May 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}

- Prozac November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, it should be
{{
if(*str1 == '\0' && *str2 == '\0') return false;
}}

because "xyz" & "xyz" is false.

- Prozac November 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

- anonymous November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I like the C++11 implementation but I didn't like the recursion, it is too expensive on big strings.

- ftonello November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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"
};

- anonymous November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Those OR expressions were fine because they work like as an 'if else' statement. The first true ends the evaluation.

- ftonello November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- anonymous November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

True.

- ftonello November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

- ftonello November 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

- DoZerg November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}

- Adam Smith November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

// 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;
}

- Sandesh December 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"); 
            }
        }

- CMUWaffles November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good catch.
I modified the condition of the second loop to be:

while (j1 > i1 || j2 > i2)

That should fix it i I think

- CMUWaffles November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- akshaymattoo November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Suppose if the given strings are "xyz" and "xz", this approach will not work.

- Raghu November 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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")

- anantpushkar009 November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Outermeasure November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

subtle bug: abs(s1.size() - s2.size()) == 1 is wrong because s1.size() returns an unsigned... The right condition is: s1.size() - s2.size() == 1 || s2.size() - s1.size() == 1

- Outermeasure November 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- cubed November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
	}
}

- Guillaume November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

    }
}

- Aron November 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}

- canejune November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- merlinme November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks merlinme, it also can reduce unnecessary looping time.

- Anonymous November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This algorithm won't work for 'abc', 'bbc'. You have to check the rest of the string, it's not possible with only one iteration. :(

- ftonello November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- billu November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- Krishna Chaitanya November 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- vallabh November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- a.md.kamil November 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- passionateCoder January 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- passionateCoder January 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
		}

- passionateCoder January 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
    }

}

- Achin Bansal January 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Nick January 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- fungled January 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
  }
}

- shiv March 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hankm2004 September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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());
}

- hankm2004 September 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));

- reevelau January 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#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;
}

- rhe29 November 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- merlinme November 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
	}

- Pavel November 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- Radu November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

- Adam Smith November 27, 2014 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More