LeetCode - 43 字符串相乘

前言

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。微博:@故胤道长）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 42 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

2. 示例

示例 1

1 2	输入: num1 = "2", num2 = "3" 输出: "6"

示例 2

1 2	输入: num1 = "123", num2 = "456" 输出: "56088"

约束条件：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

3. 答案

class MultiplyStrings {
    func multiply(_ num1: String, _ num2: String) -> String {
        let num1 = num1.reversed(), num2 = num2.reversed()
        var res = Array(repeating: 0, count: num1.count + num2.count), resStr = ""
        
        // calculate product for every digit
        for (i, char1) in num1.enumerated() {
            
            guard let digit1 = Int(String(char1)) else {
                fatalError("Invalid Input num1")
            }
            
            for (j, char2) in num2.enumerated() {
                guard let digit2 = Int(String(char2)) else {
                    fatalError("Invalid Input num2")
                }
                
                res[i + j] += digit1 * digit2
            }
        }
        
        // update digits
        for i in 0..<res.count {
            let num = res[i]
            
            res[i] = num % 10
            if i < res.count - 1 {
                res[i + 1] += num / 10
            }
            
            resStr = "\(res[i])" + resStr
        }
        
        // trim starting 0s
        while !resStr.isEmpty && resStr.first! == "0" {
            resStr.removeFirst()
        }
        
        return resStr.isEmpty ? "0" : resStr
    }
}

主要思想：反向两个字符串，并使用嵌套循环将它们与每一位数字相乘，然后使用求和和进位的思想得到最终结果。
时间复杂度： O(nm)
空间复杂度： O(n)

该算法题解的仓库：LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。

后续还会翻译大量资料到我们公众号，有感兴趣的朋友，可以加入我们。