Cracking the Coding Interview-1.5

第六版Cracking the Coding Interview题目1.5，题目如下：

One Away: There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit (or zero edits) away.

EXAMPLE
pale, ple -> true
pales. pale -> true
pale. bale -> true
pale. bake -> false

题目要求给出一个函数，判断两个字符串是否可以通过1次(或者0次)插入、删除或者替换而变为相等。首先可以知道两个字符串长度必须小于等于1才有可能满足条件。其次插入和删除两种操作其实是等价的。Python实现如下：

def oneAway(str1, str2):
    if len(str1) == len(str2):
        return oneEditReplace(str1, str2)
    elif len(str1) + 1 == len(str2):
        return oneEditInsert(str1, str2)
    elif len(str1) - 1 == len(str2):
        return oneEditInsert(str2, str1)
    return False

def oneEditReplace(str1, str2):
    edited = False
    for c1, c2 in zip(str1, str2):
        if c1 != c2:
            if edited:
                return False
            edited = True
    return True

def oneEditInsert(str1, str2):
    edited = False
    i, j = 0, 0
    while i < len(str1) and j < len(str2):
        if str1[i] != str2[j]:
            if edited:
                return False
            edited = True
            j += 1
        else:
            i += 1
            j += 1
    return True

在手机上阅读或分享本文请扫描以下二维码：

Cracking the Coding Interview-1.5

Comments