• 【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)
  • 相关阅读:
    DPDK初始化
    【20220121】Voice conversion
    win7 64位安装vs code
    Java并发编程常见面试题总结
    IOT云平台 simple(4)springboot netty实现简单的mqtt broker
    推荐一款国人开源的 Redis 可视化管理工具
    超长表单分页校验,下一页和上一页功能
    2022年软件测试经典面试真题
    centos 开机启动流程、开机运行级别
    Windows OpenGL 图像绿幕抠图
  • 原文地址:https://blog.csdn.net/njafei/article/details/126254014