Amazon Interview Question SDE1s
Country: United States
def one_edit_way(str1, str2):
len1 = len(str1)
len2 = len(str2)
if abs(len1 - len2) > 1:
return False
elif len1 == len2:
diff = 0
for i in range(0,len1):
if str1[i] != str2[i]:
diff = diff + 1
if diff == 2:
return False
return True
else:
if len1 > len2 :
i = 0
j = 0
while i < len1:
if str1[i] == str2[j]:
i = i + 1
j = j + 1
if j == len2:
return True
else:
i = i + 1
if i > j + 1:
return False
return True
else:
return one_edit_way(str2, str1)
a = "abc"
b = "ab"
c = "adc"
d = "cab"
print one_edit_way(a,b)
print one_edit_way(a,c)
print one_edit_way(a,d)
public class AmazonInterviewOne {
public static void main(String[] args) {
// TODO Auto-generated method stub
String first="abc";
String second="abcde";
int c=0;
boolean flag=true;
int lengthdiffer=first.length()>second.length()?first.length()-second.length():second.length()-first.length();
if(lengthdiffer < 1)
{int length=first.length()>second.length()?second.length():first.length();
for(int i=0;i<length;i++)
{
if(second.charAt(i)==first.charAt(i));
else
{
c++;
}
if(c>1)
{
flag=false;
break;
}
}
if (flag)
System.out.println("it is correct");
else
System.out.println("it isn't");
}
else
System.out.println("it isn't");
}
}
public class AmazonInterviewOne {
public static void main(String[] args) {
// TODO Auto-generated method stub
String first="abc";
String second="abcde";
int c=0;
boolean flag=true;
int lengthdiffer=first.length()>second.length()?first.length()-second.length():second.length()-first.length();
if(lengthdiffer < 1)
{int length=first.length()>second.length()?second.length():first.length();
for(int i=0;i<length;i++)
{
if(second.charAt(i)==first.charAt(i));
else
{
c++;
}
if(c>1)
{
flag=false;
break;
}
}
if (flag)
System.out.println("it is correct");
else
System.out.println("it isn't");
}
else
System.out.println("it isn't");
}
}
1. Check length, if difference greater than 1, return false.
2. Initialize variables differenceCount = 0, shouldInsert = false, forLoopIterationCount = 0;
3. If strings are of different length, identify which is longer. Also, differenceCount++, shouldInsert = true, forLoopIterationCount = longer.length() - 1
4. If strings are of equal length take any as longer string. shouldInsert = false, forLoopIterationCount = longer.length()
5. Iterate over the longer string till differenceCount < 2. On first mismatch, insert the mismatching character in the shorter string if shouldInsert is true (Use StringBuilder). On further mismatches, differenceCount++
6. After for loop, if differenceCount < 2, return true. Else return false.
#include<iostream>
using namespace std;
#include<conio.h>
#include<string.h>
#include<stdlib.h>
bool check(string s1, string s2)
{
int n1, n2;
n1 = s1.length();
n2 = s2.length();
if(abs(n1 - n2) > 1)
return false;
else
{
int d = 0;
if(n1 == n2)
{
for(int i=0;i<n1;i++)
{
if(s1[i]!=s2[i])
d++;
}
if(d>1)
return false;
}
else if(n1 != n2)
{
d=d+1;
for(int i=0;i<min(n1,n2); i++)
{
if(s1[i]!=s2[i])
d++;
}
if(d>1)
return false;
}
return true;
}
}
int main()
{
int t;
cout<<"cases : ";
cin>>t;
while(t--)
{
string s1, s2;
cout<<"s1 : ";
cin>>s1;
cout<<"s2 : ";
cin>>s2;
bool i = check(s1, s2);
if(i)
cout<<"yes";
else
cout<<"no";
getch();
}
}
#include<iostream>
using namespace std;
#include<conio.h>
#include<string.h>
#include<stdlib.h>
bool check(string s1, string s2)
{
int n1, n2;
n1 = s1.length();
n2 = s2.length();
if(abs(n1 - n2) > 1)
return false;
else
{
int d = 0;
if(n1 == n2)
{
for(int i=0;i<n1;i++)
{
if(s1[i]!=s2[i])
d++;
}
if(d>1)
return false;
}
else if(n1 != n2)
{
d=d+1;
for(int i=0;i<min(n1,n2); i++)
{
if(s1[i]!=s2[i])
d++;
}
if(d>1)
return false;
}
return true;
}
}
int main()
{
int t;
cout<<"cases : ";
cin>>t;
while(t--)
{
string s1, s2;
cout<<"s1 : ";
cin>>s1;
cout<<"s2 : ";
cin>>s2;
bool i = check(s1, s2);
if(i)
cout<<"yes";
else
cout<<"no";
getch();
}
}
package com.sample.amazon;
public class Edits {
public static boolean findEdit(String s1, String s2){
// Replace
if(s1.length() == s2.length()){
int replace = 0;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i) == s2.charAt(i)){
replace++;
}
}
if(replace == (s1.length()-1)){
return true;
}
}else if(s1.length()-1 == s2.length()){ // Delete
for(int i=0;i<s1.length();i++){
if(i<=s2.length()){
if(s1.charAt(i) != s2.charAt(i)){
if(s1.substring(i+1).equals(s2.substring(i))){
return true;
}else{
return false;
}
}else{
return true;
}
}
}
}else if(s1.length() == s2.length()-1){ // Insert
for(int i=0;i<s2.length();i++){
if(i<=s1.length()){
if(s2.charAt(i) != s1.charAt(i)){
if(s1.substring(i).equals(s2.substring(i+1))){
return true;
}else{
return false;
}
}
}else{
return true;
}
}
}
return false;
}
public static void main(String[] args) {
String s1 = "ABC";
String s2 = "CAB";
System.out.println(findEdit(s1, s2));
}
}
package com.sample.amazon;
public class Edits {
public static boolean findEdit(String s1, String s2){
// Replace
if(s1.length() == s2.length()){
int replace = 0;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i) == s2.charAt(i)){
replace++;
}
}
if(replace == (s1.length()-1)){
return true;
}
}else if(s1.length()-1 == s2.length()){ // Delete
for(int i=0;i<s1.length();i++){
if(i<=s2.length()){
if(s1.charAt(i) != s2.charAt(i)){
if(s1.substring(i+1).equals(s2.substring(i))){
return true;
}else{
return false;
}
}else{
return true;
}
}
}
}else if(s1.length() == s2.length()-1){ // Insert
for(int i=0;i<s2.length();i++){
if(i<=s1.length()){
if(s2.charAt(i) != s1.charAt(i)){
if(s1.substring(i).equals(s2.substring(i+1))){
return true;
}else{
return false;
}
}
}else{
return true;
}
}
}
return false;
}
public static void main(String[] args) {
String s1 = "ABC";
String s2 = "CAB";
System.out.println(findEdit(s1, s2));
}
}
package ram.examples;
public class TwoStringsOneEditAwayFromEachOther {
public static void main(String... args) throws Exception {
String str1 = "abc", str2 = "abde";
System.out.println(areTwoStringsOneEditAway(str1, str2));
}
private static boolean areTwoStringsOneEditAway(String str1, String str2) {
if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty()) {
throw new IllegalArgumentException("Invalid Inputs.");
}
int lengthDiff = Math.abs(str1.length() - str2.length());
if (lengthDiff > 1) {
return false;
}
int editCount = 0;
if (lengthDiff == 1) {
editCount++;
}
int minLength = str1.length() < str2.length() ? str1.length() : str2
.length();
for (int i = 0; i < minLength; i++) {
if (str1.charAt(i) != str2.charAt(i)) {
editCount++;
if (editCount > 1) {
return false;
}
}
}
return true;
}
}
public static void main(String[] args) {
String A="abc";
String B="cab";
boolean output=false;
if((B.length()>A.length()) || (B.length()<A.length())){
output=true;
}
else if(A.length()==B.length()){
List<Character> l=new ArrayList<>();
for(int i=0;i<A.length();i++){
l.add(A.charAt(i));
}
int t=0;
for(int i=0;i<B.length();i++){
if(l.contains(B.charAt(i))){
t++;
}
}
if(t!=A.length()){
output=true;
}
}
System.out.println(output);
}
public static void main(String[] args) {
String A="abc";
String B="cab";
boolean output=false;
if((B.length()>A.length()) || (B.length()<A.length())){
output=true;
}
else if(A.length()==B.length()){
List<Character> l=new ArrayList<>();
for(int i=0;i<A.length();i++){
l.add(A.charAt(i));
}
int t=0;
for(int i=0;i<B.length();i++){
if(l.contains(B.charAt(i))){
t++;
}
}
if(t!=A.length()){
output=true;
}
}
System.out.println(output);
}
public class CompareStrings {
private static final int MAX_DIFF_FORGIVENESS = 1;
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > MAX_DIFF_FORGIVENESS) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
char nextCharAtLonger = l< longer.length -1 ? longer[l+1] : '\0';
char nextCharAtShorter = s< shorter.length -1 ? shorter[s+1] : '\0';
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff ++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > MAX_DIFF_FORGIVENESS) {
return false;
}
}
}
return true;
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dokp", "dop"));
}
}
public class CompareStrings {
private static final int MAX_DIFF_FORGIVENESS = 1;
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > MAX_DIFF_FORGIVENESS) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
char nextCharAtLonger = l< longer.length -1 ? longer[l+1] : '\0';
char nextCharAtShorter = s< shorter.length -1 ? shorter[s+1] : '\0';
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff ++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > MAX_DIFF_FORGIVENESS) {
return false;
}
}
}
return true;
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dokp", "dop"));
}
}
public class CompareStrings {
private static final int MAX_DIFF_FORGIVENESS = 1;
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > MAX_DIFF_FORGIVENESS) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
char nextCharAtLonger = l< longer.length -1 ? longer[l+1] : '\0';
char nextCharAtShorter = s< shorter.length -1 ? shorter[s+1] : '\0';
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff ++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > MAX_DIFF_FORGIVENESS) {
return false;
}
}
}
return true;
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dokp", "dop"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dg"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dogk"));
System.out.println(CompareStrings.compareStrings("dog", "do"));
System.out.println(CompareStrings.compareStrings("dog", "dg"));
System.out.println(CompareStrings.compareStrings("dog", "dok"));
System.out.println(CompareStrings.compareStrings("dog", "dtog"));
System.out.println(CompareStrings.compareStrings("dog", "dstog"));
System.out.println(CompareStrings.compareStrings("dog", "dogst"));
System.out.println(CompareStrings.compareStrings("dog", "d"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dogk"));
System.out.println(CompareStrings.compareStrings("dog", "do"));
System.out.println(CompareStrings.compareStrings("dog", "dg"));
System.out.println(CompareStrings.compareStrings("dog", "dok"));
System.out.println(CompareStrings.compareStrings("dog", "dtog"));
System.out.println(CompareStrings.compareStrings("dog", "dstog"));
System.out.println(CompareStrings.compareStrings("dog", "dogst"));
System.out.println(CompareStrings.compareStrings("dog", "d"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dogk"));
System.out.println(CompareStrings.compareStrings("dog", "do"));
System.out.println(CompareStrings.compareStrings("dog", "dg"));
System.out.println(CompareStrings.compareStrings("dog", "dok"));
System.out.println(CompareStrings.compareStrings("dog", "dtog"));
System.out.println(CompareStrings.compareStrings("dog", "dstog"));
System.out.println(CompareStrings.compareStrings("dog", "dogst"));
System.out.println(CompareStrings.compareStrings("dog", "d"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dogk"));
System.out.println(CompareStrings.compareStrings("dog", "do"));
System.out.println(CompareStrings.compareStrings("dog", "dg"));
System.out.println(CompareStrings.compareStrings("dog", "dok"));
System.out.println(CompareStrings.compareStrings("dog", "dtog"));
System.out.println(CompareStrings.compareStrings("dog", "dstog"));
System.out.println(CompareStrings.compareStrings("dog", "dogst"));
System.out.println(CompareStrings.compareStrings("dog", "d"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dogk"));
System.out.println(CompareStrings.compareStrings("dog", "do"));
System.out.println(CompareStrings.compareStrings("dog", "dg"));
System.out.println(CompareStrings.compareStrings("dog", "dok"));
System.out.println(CompareStrings.compareStrings("dog", "dtog"));
System.out.println(CompareStrings.compareStrings("dog", "dstog"));
System.out.println(CompareStrings.compareStrings("dog", "dogst"));
System.out.println(CompareStrings.compareStrings("dog", "d"));
}
}
public class CompareStrings {
public static boolean compareStrings(String s1, String s2) {
if (s1 == null || s2 == null) {
throw new IllegalArgumentException();
}
if (Math.abs(s1.length()-s2.length()) > 1) {
return false;
}
char[] longer = s1.length() >= s2.length() ? s1.toCharArray() : s2.toCharArray();
char[] shorter = s1.length() < s2.length() ? s1.toCharArray() : s2.toCharArray();
int l = 0;
int s = 0;
int diff = 0;
String getNextChar = "";
while (s < shorter.length) {
if (longer[l] == shorter[s] ) {
l++;s++;
} else {
int nextCharAtLonger = getNextChar(longer, l);
int nextCharAtShorter = getNextChar(shorter, s);
if (nextCharAtLonger == shorter[s]) { // inserted
l++;
diff++;
} else if (nextCharAtLonger == nextCharAtShorter){ // replaced
l++;
s++;
diff++;
} else {
return false;
}
if (diff > 1) {
return false;
}
}
}
return true;
}
private static char getNextChar(char[] chars, int index) {
return index < chars.length - 1 ? chars[index+1] : '\0';
}
public static void main(String[] argv) {
System.out.println(CompareStrings.compareStrings("dog", "dogk"));
System.out.println(CompareStrings.compareStrings("dog", "do"));
System.out.println(CompareStrings.compareStrings("dog", "dg"));
System.out.println(CompareStrings.compareStrings("dog", "dok"));
System.out.println(CompareStrings.compareStrings("dog", "dtog"));
System.out.println(CompareStrings.compareStrings("dog", "dstog"));
System.out.println(CompareStrings.compareStrings("dog", "dogst"));
System.out.println(CompareStrings.compareStrings("dog", "d"));
}
}
public static boolean areStringsOneEditFromEachOther(String a, String b) {
if (a == null || b == null || a.isEmpty() || b.isEmpty() || Math.abs(a.length() - b.length()) > 1) {
return false;
}
if (a.contains(b)) {
return true;
}
if (a.length() == b.length()) {
for (int i = 0; i < a.length(); i++) {
char[] aCharacters = a.toCharArray();
char[] bCharacters = b.toCharArray();
aCharacters[i] = '-';
bCharacters[i] = '-';
String newA = new String(aCharacters);
String newB = new String(bCharacters);
if (newA.equals(newB)) {
return true;
}
}
} else {
String larger = a.length() > b.length() ? a : b;
String smaller = a.length() < b.length() ? a : b;
for (int i = 0; i < larger.length(); i++) {
String reducedString = "";
for (int j = 0; j < larger.length(); j++) {
if (i != j) {
reducedString += larger.charAt(j);
}
}
if (reducedString.equals(smaller)) {
return true;
}
}
}
return false;
}
public bool CheckIfStringsHaveOneEditDifference(string input1, string input2)
{
if (string.IsNullOrEmpty(input1) && string.IsNullOrEmpty(input2)) return true;
if (input1 == null) return false;
if (input2 == null) return false;
if (input1.Length - input2.Length > 1) return false;
//// 1. Check that both strings contains same set of chars.
Dictionary<char, int> dic = new Dictionary<char, int>();
for (int i = 0; i < input1.Length; i++)
{
if (dic.ContainsKey(input1[i]))
{
dic[input1[i]] = dic[input1[i]] + 1;
}
else
{
dic.Add(input1[i],1);
}
}
for (int i = 0; i < input2.Length; i++)
{
if (dic.ContainsKey(input2[i]))
{
dic[input2[i]] = dic[input2[i]] - 1;
}
else
{
dic[input2[i]] = -1;
}
}
int totalDiff = 0;
foreach (var i in dic)
{
totalDiff = totalDiff + Math.Abs(i.Value);
}
//// If total diff is > 1 return false
if (totalDiff > 1)
return false;
//// 2. If both strings are of same length. Match char to char and
int diff = 0;
if (input1.Length == input2.Length)
{
for (int i = 0; i < input1.Length; i++)
{
if (input1[i] != input2[i])
{
diff++;
}
}
}
//// if more than 1 diff, return false.
if (diff > 2) return false;
//// 3. If the length is not same. make sure the strings can be made same by one char delete.
//// "abc" and "adbc" are valid. only one edit required - delete 'd'
//// "abc" and "adcb" are not valid. two edits required - delete 'd' and swap 'c' and 'b'
if (input1.Length > input2.Length)
{
var temp = input1;
input1 = input2;
input2 = input1;
}
int index1 = 0;
int index2 = 0;
diff = 0;
while (index1 < input1.Length)
{
if (input1[index1] == input2[index2])
{
index1++;
index2++;
}
else
{
index2++;
diff++;
}
if (diff > 1)
return false;
}
return true;
}
public bool CheckIfStringsHaveOneEditDifference(string input1, string input2)
{
if (string.IsNullOrEmpty(input1) && string.IsNullOrEmpty(input2)) return true;
if (input1 == null) return false;
if (input2 == null) return false;
if (input1.Length - input2.Length > 1) return false;
//// 1. Check that both strings contains same set of chars.
Dictionary<char, int> dic = new Dictionary<char, int>();
for (int i = 0; i < input1.Length; i++)
{
if (dic.ContainsKey(input1[i]))
{
dic[input1[i]] = dic[input1[i]] + 1;
}
else
{
dic.Add(input1[i],1);
}
}
for (int i = 0; i < input2.Length; i++)
{
if (dic.ContainsKey(input2[i]))
{
dic[input2[i]] = dic[input2[i]] - 1;
}
else
{
dic[input2[i]] = -1;
}
}
int totalDiff = 0;
foreach (var i in dic)
{
totalDiff = totalDiff + Math.Abs(i.Value);
}
//// If total diff is > 1 return false
if (totalDiff > 1)
return false;
//// 2. If both strings are of same length. Match char to char and
int diff = 0;
if (input1.Length == input2.Length)
{
for (int i = 0; i < input1.Length; i++)
{
if (input1[i] != input2[i])
{
diff++;
}
}
}
//// if more than 1 diff, return false.
if (diff > 2) return false;
//// 3. If the length is not same. make sure the strings can be made same by one char delete.
//// "abc" and "adbc" are valid. only one edit required - delete 'd'
//// "abc" and "adcb" are not valid. two edits required - delete 'd' and swap 'c' and 'b'
if (input1.Length > input2.Length)
{
var temp = input1;
input1 = input2;
input2 = input1;
}
int index1 = 0;
int index2 = 0;
diff = 0;
while (index1 < input1.Length)
{
if (input1[index1] == input2[index2])
{
index1++;
index2++;
}
else
{
index2++;
diff++;
}
if (diff > 1)
return false;
}
return true;
}
/* ZoomBA
1. When both strings have same length
> Check if they differ in only one char
2. When both strings differ in length
> Check if they differ only by 1 size
> larger can be created by a split of the smaller:
> larger = smaller_1 new_char smaller_2
*/
def same_length(string1, string2){
counter = 0
!exists ( [0: #|string1| ] ) :: {
counter += ( ( string1[$.o] != string2[$.o] ) ? 1 : 0 )
counter > 1 // updates local, seeded by global
}
}
def diff_length( smaller , larger ){
first_diff = index ( [0:#|smaller|] ) :: {
smaller[$.o] != larger[$.o] }
// from first diff, everything else should match
!exists ( [first_diff : #|smaller| ] ) :: {
smaller[$.o] != larger[$.o + 1 ] }
}
def one_distant_apart( s1, s2 ){
l1 = #|s1| ; l2 = #|s2|
if ( #|l1 -l2 | > 1 ) return false
if ( l1 == l2 ) { return same_length( s1, s2 ) }
if ( l1 < l2 ){ return diff_length ( s1, s2 ) }
return diff_length ( s2, s1 )
}
In general case we can just compute Levenshtein distance in O(n^2), and mem O(n), but in this case we can do simple O(n) by just splitting cases.
- emb September 07, 2015def is_edit_distance_1(s1, s2): # tell if only one character differs if len(s1) == len(s2): return sum(c1 != c2 for (c1, c2) in zip(s1, s2)) == 1 elif abs(len(s1) - len(s2)) > 1: return False else: if len(s1) > len(s2): s1, s2 = s2, s1 # alright, now there is one extra character in s2 i = j = 0 while i < len(s1): if s1[i] == s2[j]: i += 1 j += 1 # We haven't met an extra character before elif i == j: j += 1 # Oops, two extra characters, exit else: return False return True assert is_edit_distance_1('abc', 'adc') assert is_edit_distance_1('abc', 'ab') assert not is_edit_distance_1('abc', 'acb') assert not is_edit_distance_1('abc', 'cab') assert is_edit_distance_1('abc', 'abcd') assert is_edit_distance_1('abcd', 'abc')