Skip to content

Latest commit

 

History

History

day7

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

cover

Day 7 -- One Edit Away

Question -- Given two strings, check whether they are one edit distance apart, i.e., if str1 and str2 are the given strings, check whether str1 can be converted to str2 with exactly one edit.

An edit between 2 strings is one of the following operations

  1. Replace a character
  2. Add a character
  3. Delete a character

Also note that two same strings are also one edit away since we can say that anyone of those strings can be converted into another by just one replace operation where we replace any of the character by itself.

Example

Input:
  str1 = 'abc', str2 = 'abc'
Output: yes
Input:
  str1 = 'abc', str2 = 'abd'
Output: yes
Input:
  str1 = 'abc', str2 = 'ab'
Output: yes
Input:
  str1 = 'abc', str2 = 'abcd'
Output: yes
Input:
  str1 = 'abc', str2 = 'abdef'
Output: no

ques

JavaScript Implementatiom

/**
 * @author MadhavBahl
 * @date 28/12/2018
 * METHOD - Consider the 3 cases separately,
 *   1) If difference in lengths is more than 1 then print no and exit
 *   2) If the length is same and the hamming distance is 1, print yes
 *   3) If difference in length equals 1, then loop through the bigger string and check for the corresponding elements of smaller string
 */

function oneEditAway (str1, str2) {
    let len1 = str1.length,
        len2 = str2.length;

        if (Math.abs(len1-len2) > 1) {
            // If difference in lengths is greater than 1
            console.log (`Strings "${str1}" and "${str2}" are not one edit away`);
            return 0;
        } else if(len1 === len2) {
            // if lengths are equal
            let count = 0;

            for (let i=0; i<len1; i++) {
                if (str1[i] !== str2[i])    count++;
            }

            if (count < 2) {    // hamming distance is 0 or 1
                console.log (`Strings "${str1}" and "${str2}" are one edit away`);
                return 1;
            } else {            // hamming distance >= 2
                console.log (`Strings "${str1}" and "${str2}" are not one edit away`);
                return 0;
            }

        } else {
            // Difference in lenghts = 1
            if (len1 > len2)    return checkOneEdit (str1, str2);
            else    return checkOneEdit (str2, str1);
        }
}

function checkOneEdit (str1, str2) {
    let edit = 0, j=0;
    for (let i=0; i<str1.length; i++) {
        if (str1[i] !== str2[j]) {
            edit++;
        } else {
            j++;
        }
    }

    if (edit >= 2) {
        console.log (`Strings "${str1}" and "${str2}" are not one edit away`);
        return 0;
    } else {
        console.log (`Strings "${str1}" and "${str2}" are one edit away`);
        return 1;
    }
}

// Test Cases
oneEditAway ('abc', 'abc'); // true
oneEditAway ('abc', 'abd'); // true
oneEditAway ('abc', 'ab'); // true
oneEditAway ("a", "a");  // true
oneEditAway ("abcdef", "abqdef");  // true
oneEditAway ("abcdef", "abccef");  // true
oneEditAway ("abcdef", "abcde");  // true
oneEditAway ("aaa", "abc");  // false
oneEditAway ('bc', 'abc'); // true
oneEditAway ('abc', 'abced'); // false

Python Implementatiom

"""
  @author : vishalshirke7
  @date : 28/12/2018

  Method - There are 2 test cases
      1) Difference of length between 2 characters is more than one, then answer is False
      2) Traverse both the strings simultaneously
          2.1) if characters at 1st position in both strings doesn't match then increment count and if 
               it is greater than one return False
              2.1.1) increment the pointer of max length string else if equal increment both pointers
          2.2) If characters match then increment both pointers
      3) Lastly increment count if any extra remaining character is present in any string
      4) Return True if count is either 0 or 1 else return False
            
"""

def check_one_edit_away(str1, str2):
    l1, l2 = len(str1), len(str2)
    if abs(l1 - l2) > 1:
        return False
    count = 0
    i, j = 0, 0
    while i < l1 and j < l2:
        if str1[i] != str2[j]:
            if count == 1:
                return False

            if l1 > l2:
                i += 1
            elif l2 > l1:
                j += 1
            else:
                i += 1
                j += 1

            count += 1
        else:
            i += 1
            j += 1
    
    # check for last remaining character in any string, if length are not equal
    if i < l1 or j < l2: 
        count += 1

    return count <= 1


check_one_edit_away(*(input().split())) # here list unpacking is used
"""
  @author : imkaka
  @date : 28/12/2018
"""
# Merges the Insert/Remove and Replace Operation in One.
# Insert and Remove are Identical Operation logically.

import sys
import math


def oneEditDistance(str1, str2):
    if(abs(len(str1) - len(str2)) > 1):
        return False
    short = str1 if len(str1) < len(str2) else str2
    longg = str1 if len(str1) > len(str2) else str2

    id1 = 0
    id2 = 0
    flag = False

    while(id2 < len(longg) and id1 < len(short)):
        if(short[id1] != longg[id2]):
            if(flag):
                return False
            flag = True
            if(len(short) == len(longg)):
                id1 += 1
        else:
            id1 += 1
        id2 += 1
    return True


def main():
    strings = input().split(' ')
    str1 = strings[0]
    str2 = strings[1]

    print(f"{str1} , {str2} : {oneEditDistance(str1, str2)}.")

    print(f" {'abcd'} , {'acd'} : {oneEditDistance('abcd', 'acd')}.")
    print(f"{'cake'} , {'bake'} : {oneEditDistance('cake', 'bake')}.")
    print(f"{'sue'} , {'chikuu'}: {oneEditDistance('sue', 'chikuu')}.")


if __name__ == '__main__':
    main()

C++ Implementation

/*
* @author : dhruv-gupta14
* @date : 28/12/2018
*/

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int flag=0,x=0;
    string str1;
    getline(cin,str1);

    string str2;
    getline(cin,str2);

    int n = str1.length();
    int m = str2.length();

    if(str1 == str2)
        cout << "Yes";
    else if(n==m && str1 !=str2){
        for(int i=0; i<n; i++)
        {
            if(str1[i] != str2[i])
                flag++;
        }
        if(flag == 1)
            cout << "Yes";
        else
            cout << "No";
    } else{
        if(n == m+1)
        {
            x=0;
            for(int j=0; j<n; j++)
            {
                if(str1[j] != str2[x])
                {
                    flag++;
                }else{
                    x++;
                }
            }
        }else if(m == n+1){
            x=0;
            for(int k=0; k<m; k++)
            {
                if(str1[x] != str2[k])
                {
                    flag++;
                }else{
                    x++;
                }
            }
        }
        if(flag == 1)
            cout << "Yes";
        else
            cout << "No";
    }

    return 0;
}
/*
* @author : imkaka
* @date   : 28/12/2018
*/

#include<iostream>
#include<string>

using namespace std;

string isOneEditDistanceAway(string str1, string str2){

    int mi = str1.size() <= str2.size() ? str1.size() : str2.size();
    int ma = str1.size() > str2.size() ? str1.size() : str2.size();
    if( (ma - mi) > 1){
        return " No! ";
    }

    string sho = str1.size() < str2.size() ? str1 : str2;
    string lon = str1.size() > str2.size() ? str1 : str2;

    bool diff = false;
    int id1 = 0;
    int id2 = 0;

    while(id2 < lon.size() && id1 < sho.size()){

        if(sho[id1] != lon[id2]) {

            if(diff) return "No!";
            diff = true;

            if(sho.size() == lon.size()){
                id1++;
            }
        }else{
            id1++;
        }
        id2++;
    }
    return "Yes!";
}

int main(){

    string str1 , str2;

    cout << "Enter two strings with space in between: ";
    cin >> str1 >> str2;

    cout << str1 << " " << str2 << " => " <<isOneEditDistanceAway(str1, str2) << endl;
    cout << "======= Hard Coded Strings ======= " << endl;
    cout << "pale" << " pal" << " " << " => " <<isOneEditDistanceAway("pale", "pal") << endl;
    cout << "bake" << " cake" << " " << " => " <<isOneEditDistanceAway("bake", "cake") << endl;

    return 0;
}
/*
 * @author: aaditkamat
 * @date: 28/12/2018
 */

#include <iostream>

using namespace std;

bool can_replace_a_character(string str1, string str2) {
    if (str1.size() != str2.size()) {
        return false;
    }

    int change = 0;
    
    for (int i = 0; i < str1.size(); i++) {
        if (str1[i] != str2[i]) {
            change++;
        }
    }
    
    return change == 1;
}

bool is_a_modified_substring(string str1, string str2) {
    if (str1.empty()) {
        return true;
    }

    if (str1[0] != str2[1] && str1[0] != str2[0]) {
        return false;
    }

    int found = str2.find(str1[0]);
    
    if (found == 1) {
        return str2.find(str1) != string::npos;
    }

    int j = 0, ctr = 0;
    for (int i = 0; i < str1.size(); j++) {
        if (j >= str2.size()) {
                return false;
        }
        if (str1[i] != str2[j] && ctr == 0) {
            ctr++;
            continue;
        }
        if (str1[i] != str2[j]) {
            return false;
        }
        i++;
    }
    return true;
}

bool can_add_a_character(string str1, string str2) {
    return str2.size() - str1.size() == 1 && is_a_modified_substring(str1, str2);  
}

bool can_delete_a_character(string str1, string str2) {
    return str1.size() - str2.size() == 1 && is_a_modified_substring(str2, str1);
}

bool are_one_edit_away(string str1, string str2) {
    if (str1 == str2) {
        return true;
    }
    return can_replace_a_character(str1, str2) || can_add_a_character(str1, str2) || can_delete_a_character(str1, str2);
}

int main() {
    string str1, str2;
    cout << "Enter two strings: " << endl;
    getline(cin, str1);
    getline(cin, str2);
    cout << "Are \"" << str1 << "\" and \"" << str2 << "\" one edit away? " << are_one_edit_away(str1, str2) << endl;
}
/**
 * @author:divyakhetan
 * @date: 30/12/2018
 */


#include<bits/stdc++.h>
using namespace std;

int min(int x, int y, int z) 
{ 
    return min(min(x, y), z); 
} 

int main(){
	string s1, s2;
	cin >> s1 >> s2;
	
	int m = s1.length();
	int n = s2.length();
	int edit[m + 1][n + 1]; 
	
	for(int i = 0; i <= n; i++){
		edit[0][i] = i;
	}
	
	
	for(int i = 0; i <= m; i++){
		edit[i][0] = i;
	}
	
	for(int i =  1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			if(s1[i - 1] == s2[j - 1]) edit[i][j] = edit[i -1 ][j - 1];
			else edit[i][j] = 1 + min(edit[ i -1][j], edit[i - 1][j - 1], edit[i][j - 1]);  
		}
	}
	
	if(edit[m][n] <= 1) cout << "At edit distance 1";
	else cout << "Not at edit distance 1";
	return 0;
}
/*
  *@author: profgrammer
  *@date: 31-12-2018
*/

#include <bits/stdc++.h>
#define inf 100000000
using namespace std;

string s1, s2;

int dp[1500][1500];

// function that returns minimum edits required to convert s1[0 .. i-1] into s2[0 .. j-1]
int minEdit(int i, int j){
  // base cases. if s1 finishes we need j insertions, if s2 finishes we need i insertions
  if(i == 0) return j;
  if(j == 0) return i;
  // housekeeping for dp with memoisation
  if(dp[i][j] != inf) return dp[i][j];
  // if the last characters are the same, no need to change anything and move both pointers by 1 unit
  if(s1[i-1] == s2[j-1]) {
    return dp[i][j] = minEdit(i-1, j-1);
  }
  // replace s1[i] to be s2[j]. the strings to be checked are still s1[0 .. i-1] and s2[0 .. j-1] but the cost is +1
  int minReplace = 1 + minEdit(i-1, j-1);
  // delete s1[i], cost is +1 and the strings are now s1[0 .. i-1] and s2[0 .. j] because we need to compare the i-1th character with the jth character
  int minDelete = 1 + minEdit(i-1, j); 
  // insert a character into s1 at index i. cost is +1 and now the strings to be checked are s1[0 .. i] because the ith character isn't compared yet and s2[0 .. j-1]
  int minInsert = 1 + minEdit(i, j-1);
  // return min of these 3 values
  return dp[i][j] = min(minReplace, min(minDelete, minInsert));
}

int main() {
  for(int i = 0;i < 1500;i++){
    for(int j = 0;j < 1500;j++) dp[i][j] = inf;
  }
  cin>>s1>>s2;
  if(minEdit(s1.size(), s2.size()) <= 1) cout<<"The strings are 1 edit away\n";
  else cout<<"The strings are not 1 edit away\n";
}

C Implementation

/**
 * @author: Rajdeep Roy Chowdhury<[email protected]>
 * @github: https://github.com/razdeep
 * @date: 24/12/2018
 */

#include <stdio.h>
#include <string.h>
int replacable(const char *s1, const char *s2)
{
    int diff_count = 0;
    int s1_len = strlen(s1);
    int s2_len = strlen(s2);
    if (s1_len == s2_len)
    {
        for (int i = 0; i < s1_len; i++)
        {
            if (s1[i] != s2[i])
                diff_count++;
        }
        if (diff_count == 1)
            return 1;
    }
    return 0;
}
int addable(const char *s1, const char *s2)
{
    int diff_count = 0;
    int s1_len = strlen(s1);
    int s2_len = strlen(s2);
    if (s1_len == s2_len + 1)
    {
        int j = 0;
        for (int i = 0; i < s1_len; i++)
        {
            if (s1[i] == s2[j])
            {
                j++;
            }
            else
            {
                diff_count++;
            }
        }
        if (diff_count <= 1)
            return 1;
        else
            return 0;
    }
    return 0;
}
int deletable(const char *s1, const char *s2)
{
    int diff_count = 0;
    int s1_len = strlen(s1);
    int s2_len = strlen(s2);
    if (s1_len + 1 == s2_len)
    {
        int j = 0;
        for (int i = 0; i < s2_len; i++)
        {
            if (s2[i] == s1[j])
            {
                j++;
            }
            else
            {
                diff_count++;
            }
        }
        if (diff_count <= 1)
            return 1;
        else
            return 0;
    }
    return 0;
}
int main()
{
    char s1[100], s2[100];
    printf("Enter the first string ");
    scanf("%s", s1);
    printf("Enter the second string ");
    scanf("%s", s2);
    if (strcmp(s1, s2) == 0 || replacable(s1, s2) || addable(s1, s2) || deletable(s1, s2))
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}
/* *
   * @author : ashwek
   * @date : 29/12/2018
   */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int oneEditAway(char Str1[], char Str2[]){

    int l1 = strlen(Str1), l2 = strlen(Str2);
    int i=0, j=0, diff=0;

    if( abs(l1 - l2) > 1 )
        return 0;

    while( diff<2 && (i < l1) && (j < l2) ){

        if( Str1[i] == Str2[j] ){
            i++;
            j++;
        }
        else{
            diff++;
            if( l1 == l2 ){
                i++;
                j++;
            }
            else if( l1 < l2 )
                j++;
            else
                i++;
        }
    }

    return diff < 2;

}

void main(){

    char Str1[20];
    char Str2[20];

    printf("Enter string 1 = ");
    scanf("%s", Str1);
    printf("Enter string 2 = ");
    scanf("%s", Str2);

    printf("%s & %s are ", Str1, Str2);
    if( oneEditAway(Str1, Str2) == 0 )
        printf("NOT ");
    printf("one edit away\n");
}

Java Implementation

/**
 * @author: aaditkamat
 * @date: 28/12/2018
 */
import java.util.Scanner;

class OneEditAway {
    static boolean canReplaceACharacter(String str1, String str2) {
        if (str1.length() != str2.length()) {
            return false;
        }
        int change = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                change++;
            }
        }
        return change == 1;
    }

    static boolean isASubstring(String str1, String str2) {
        if (str1.isEmpty()) {
            return true;
        }

        if (str1.charAt(0) != str2.charAt(1) && str1.charAt(0) != str2.charAt(0)) {
            return false;
        }

        int found = str2.indexOf(str1.charAt(0));
        
        if (found == 1) {
            return str2.substring(1).equals(str1);
        }

        int j = 0, ctr = 0;
        for (int i = 0; i < str1.length(); j++) {
            if (j >= str2.length()) {
                return false;
            }
            if (str1.charAt(i) != str2.charAt(j) && ctr == 0) {
                ctr++;
                continue;
            }
            if (str1.charAt(i) != str2.charAt(j)) {
                return false;
            }
            i++;
        }
        return true;        
    }

    static boolean canAddACharacter(String str1, String str2) {
        return str2.length() - str1.length() == 1 && isASubstring(str1, str2);  
    }

    static boolean canDeleteACharacter(String str1, String str2) {
        return str1.length() - str2.length() == 1 && isASubstring(str2, str1);
    }

    static boolean areOneEditAway(String str1, String str2) {
        if (str1.equals(str2)) {
            return true;
        }
        return canReplaceACharacter(str1, str2) || canAddACharacter(str1, str2) || canDeleteACharacter(str1, str2);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str1, str2;
        System.out.println("Enter two strings: ");
        str1 = input.next();
        str2 = input.next();
        System.out.printf("Are \"%s\" and \"%s\" one edit away? %b\n", str1, str2, areOneEditAway(str1, str2)); 
    }
}

Java Implementation

/**
 * @date 28/12/18
 * @author SPREEHA DUTTA
 */
import java.util.*;
public class Edit {
    public static void main(String []args)
    {
        Scanner sc=new Scanner(System.in);
        String s1,s2;int l,c=0;char b;int i;
        System.out.println("Enter two strings ");
        s1=sc.next();
        s2=sc.next();
        
        if(Math.abs(s1.length()-s2.length())<=1)
        {
            if(s1.length()<s2.length())
                l=s1.length();
            else
                l=s2.length();
            for(i=0;i<l;i++)
            {
                if(s1.charAt(i)==s2.charAt(i))
                    c++;
            }
            if((c==l)||((c+1)==l && (s1.length()==s2.length())))
                System.out.println(s1+" and "+s2+" are one edit away");
            else
                System.out.println(s1+" and "+s2+" are not one edit away ");
        }
        else
                System.out.println(s1+" and "+s2+" are not one edit away ");
    }
}

Ruby Implementation

=begin
@author: aaditkamat
@date: 28/12/2018
=end

def can_replace_a_character(str1, str2) 
    if (str1.size() != str2.size()) 
        return false
    end
    change = 0
    (str1.size()).times do |i|
        if (not str1[i] === str2[i]) 
            change += 1
        end
    end 
    return change === 1
end

def is_a_substring(str1, str2) 
    if (str1.empty?)
        return true
    end

    if (not str1[0] === str2[1] and not str1[0] === str2[0]) 
        return false
    end

    found = str2.index(str1[0])
        
    if (found == 1) 
        return str2[1..str2.length][str1] === str1
    end

    i = 0
    j = 0
    ctr = 0
    until i >= str1.length do 
        if j >= str2.length
            return false
        end
        if (not str1[i] === str2[j] and ctr === 0) 
            ctr += 1
            j += 1
            next
        end
        if (not str1[i] === str2[j]) 
            return false
        end
        i += 1
        j += 1
    end
    true
end

def can_add_a_character(str1, str2) 
    str2.size() - str1.size() === 1 and is_a_substring(str1, str2)  
end

def can_delete_a_character(str1, str2) 
    str1.size() - str2.size() === 1 and is_a_substring(str2, str1)
end

def are_one_edit_away(str1, str2) 
    if (str1 === str2) 
        return true
    end
    can_replace_a_character(str1, str2) or can_add_a_character(str1, str2) or can_delete_a_character(str1, str2)
end 

def main
    puts "Enter two strings: "
    str1 = gets().chomp!
    str2 = gets().chomp!
    puts "Are \"#{str1}\" and \"#{str2}\" one edit away? #{are_one_edit_away(str1, str2)}"
end

main

Have Another solution?

The beauty of programming lies in the fact that there is never a single solution to any problem.

In case you have an alternative way to solve this problem, do contribute to this repository (https://github.com/CodeToExpress/dailycodebase) :)