• 【Swift算法学习】 LeetCode 同构字符串


    题目

    同构字符串

    给定两个字符串 s 和 t ,判断它们是否是同构的。

    如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。

    每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身。

    示例 1:

    输入:s = “egg”, t = “add”
    输出:true
    示例 2:

    输入:s = “foo”, t = “bar”
    输出:false
    示例 3:

    输入:s = “paper”, t = “title”
    输出:true

    提示:

    1 <= s.length <= 5 * 104
    t.length == s.length
    s 和 t 由任意有效的 ASCII 字符组成

    思路

    这一题主要使用map的形式来记录一对一的关系,保证 a:b类似的关系是固定的,这里要注意,a:b是双向绑定的,a:b 则 b:b 就不可以

    代码

    func isIsomorphic(_ s: String, _ t: String) -> Bool {
            var map : [Character : Character] = [:]
            for i in 0..
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    这样写完之后,发现超时,查了下s.index(s.startIndex, offsetBy: i) 这种写法效率太低,这里建议使用zip写法(或者string 转成 array),如下

    func isIsomorphic(_ s: String, _ t: String) -> Bool {
            var map : [Character : Character] = [:]
    
            for (char1,char2) in zip(s, t) {
                if let target = map[char1] {
                    if target != char2 {
                        return false
                    }
                } else {
                    if map.values.contains(char2) {
                        return false
                    }
                    map[char1] = char2
                }
             }
    
            return true
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    总结

    执行用时:4 ms, 在所有 Swift 提交中击败了100.00%的用户
    内存消耗:14.3 MB, 在所有 Swift 提交中击败了70.45%的用户

    这里有两个注意事项

    • swift string的读写效率问题
    • 双向绑定,单项的绑定需要判断下 map.values.contains(char2)
  • 相关阅读:
    C++前缀和算法的应用:用地毯覆盖后的最少白色砖块 原理源码测试用例
    二分搜索树节点删除(Java 实例代码)
    浏览器上的快捷键
    Tf铁蛋白颗粒包载顺铂/奥沙利铂/阿霉素/甲氨蝶呤MTX/紫杉醇PTX等药物
    ros协议的最佳解决方案
    mybatis中#{}和${}的区别
    Kubernetes (K8S) 1.24.3 For Ubuntu 安装
    【C++】C++入门
    以太网中的介质共享访问控制机制
    单链表的基本操作(C语言+图解分析)
  • 原文地址:https://blog.csdn.net/njafei/article/details/126254014