检验Swift中两个值是否同构

Question

解决书本上的问题

编写一个接受两个值的函数，如果它们是同构的，则返回true。也就是说，值的每一部分必须精确地映射到另一部分，但这可能是它本身。提示:如果可以用另一个字母替换每个字母的所有实例，则字符串A和B被认为是同构的。例如，“侵权”和“泵”是同构的，因为你可以用P代替t，用U代替O，用M代替R，这样1231和4564是同构数。对于数组，您比较元素，因此1，2，1和4、8、4是同构的。

作者建议将两个值转换为字符串，然后存储将每个字符映射到另一个字符的字典。

func challenge57(first firstValue: Any, second secondValue: Any) -> Bool {
    let first = String(describing: firstValue)
    let second = String(describing: secondValue)
    
    guard first.count == second.count else { return false }
    
    var characterMap = [Character: Character]()
    let firstArray = Array(first)
    let secondArray = Array(second)
    
    for (index, character) in firstArray.enumerated() {
        let correspondingCharacter = secondArray[index]
        
        if let currentMapping = characterMap[character] {
            if currentMapping != correspondingCharacter {
                return false
            }
        } else {
            if characterMap.values.contains(correspondingCharacter) {
                return false
            }
            
            characterMap[character] = correspondingCharacter
        }
    }
    
    return true
}

然而，contains()是一个线性时间运算，使整个方法是二次的，我正在努力想出一个优化方案。很想听到任何正确方向的指导。

Answer 1

审查您的代码

这可能是个人品味的问题，但我认为guard是一种语言功能，以避免“如果-让厄运金字塔”或检查特殊情况，但不是作为否定条件的一般替代。在其他作品中，我会写

guard first.count == second.count else { return false }

作为

if first.count != second.count { return false }

首先将字符串转换为数组，如果以后需要按字符位置下标，这是个好主意，如

let correspondingCharacter = secondArray[index]

但是这两个字符串中的字符是按顺序访问的，因此可以并行地枚举字符并保存附加的数组存储：

for (character, correspondingCharacter) in zip(first, second) { ... }

费时

if characterMap.values.contains(correspondingCharacter)

如果我们将第二个字符串中看到的所有字符的集合保持为far，则可以避免。在集合中插入一个字符并检查它是否已经存在，可以通过一个调用来完成。

您还应该选择一个更具描述性的函数名。

然后，代码将如下所示：

func isomorphic(first firstValue: Any, second secondValue: Any) -> Bool {
    let first = String(describing: firstValue)
    let second = String(describing: secondValue)
    
    if first.count != second.count { return false }

    // Map from characters in the first string to characters in the second string:
    var characterMap = [Character: Character]()
    // All characters seen in the second string so far:
    var seen = Set<Character>()
    
    for (firstChar, secondChar) in zip(first, second) {
        if let currentMapping = characterMap[firstChar] {
            if currentMapping != secondChar { return false }
        } else {
            if !seen.insert(secondChar).inserted { return false }
            characterMap[firstChar] = secondChar
        }
    }
    
    return true
}

我也(通常)更喜欢把语句分块放在单独的行上。

if first.count != second.count {
    return false
}

但这又是个人品味的问题。调试期间的一个优点是可以更容易地在该语句上设置断点。

对问题描述和API

的回顾

如果两个字符串的字符之间存在一对一的对应关系，那么就可以说它们是同构的。如果数组的各个元素可以被比较为相等，也就是如果数组元素符合Equatable协议，这对数组也是有意义的。

更普遍地说，“值的每一部分必须精确地映射到另一部分”对于集合(其元素具有可比性)来说是有意义的。

但是(在我看来)为任意的值定义这种“同构”是没有意义的。当然，您可以使用String(describing:)将任何值转换为字符串，但是

• 除非这些值符合CustomStringConvertible或相关协议，否则结果不指定，并且
• 即使所有的值都符合CustomStringConvertible，结果也可能不是人们所期望的。

说明第二点的例子：

• 即使数组是同构的，challenge57(first: [11, 2], second: [3, 44])的计算结果也是false，因为它们的字符串表示不是同构的。
• 即使第一个数组的每个元素都可以唯一地映射到第二个数组的一个元素，但challenge57(first: [1, 2], second: ["1", "2"])的计算结果仍然是false。
• challenge57(first: [], second: "12")的计算结果为true，因为空数组的字符串表示恰好与"12“同构。

因此，我认为一个更好的API应该是

func isomorphic<C1, C2>(first: C1, second: C2) -> Bool 
where C1: Collection, C1.Element: Equatable, C2: Collection, C2.Element: Equatable

缺点是我们不能再使用字典和集合来进行更快的查找。但是，我们可以对hashable元素进行专门化，这与上面的代码没有太大的不同：

func isomorphic<C1, C2>(first: C1, second: C2) -> Bool 
where C1: Collection, C1.Element: Hashable, C2: Collection, C2.Element: Hashable {
    if first.count != second.count {
        return false
    }
    
    // Map from elements in the first collection to characters in the second collection:
    var map = [C1.Element: C2.Element]()
    // All elements seen in the second collection so far:
    var seen = Set<C2.Element>()
    
    for (firstElement, secondElement) in zip(first, second) {
        if let currentMapping = map[firstElement] {
            if currentMapping != secondElement { return false }
        } else {
            if !seen.insert(secondElement).inserted { return false }
            map[firstElement] = secondElement
        }
    }

    return true
}

这与字符串和数组的预期效果一样：

print(isomorphic(first: "tort", second: "pump")) // true
print(isomorphic(first: "1234", second: 1234)) // Syntax error
print(isomorphic(first: [11, 2], second: [3, 44])) // true
print(isomorphic(first: [1, 2], second: ["1", "2"])) // true

定义两个整数是同构的，如果它们的十进制数之间有一对一的对应，我觉得有点武断。(为什么是十进制数字而不是二进制数字？负数呢？)。但是如果需要的话，我会将其作为一个函数重载来分离：

func isomorphic(first: Int, second: Int) -> Bool {
    return isomorphic(first: String(first), second: String(second))
}

print(isomorphic(first: 1231, second: 4564)) // true