LeetCode 43.字符串相乘

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

方法一、做加法

一图胜前言，主要完成错位相加即可，注意边界情况的处理。此方法非直接将输入转换为整数，但是其中一位会转换为整数，符合题目要求。

Swift

func multiply(_ num1: String, _ num2: String) -> String {
        if num1 == "0" || num2 == "0" {
            return "0"
        }
        
        var ans = "0"
        let m = num1.count
        let n = num2.count
        
        for i in (0..<n).reversed() {
            var add = 0//进位
            var curr = [Int]()
            
            //补0
            for j in (0..<n).reversed() {
                if j > i {
                    curr.append(0)
                }
            }
            
            let char = num2[num2.index(num2.startIndex, offsetBy: i)]
            let y = Int(String(char))!//乘数的一位
            
            for j in (0..<m).reversed() {
                let char = num1[num1.index(num1.startIndex, offsetBy: j)]
                let x = Int(String(char))!//被乘数的一位
                
                let result = x * y + add;
                curr.append(result % 10)
                add = result / 10
            }
            
            while add != 0 {
                curr.append(add % 10)
                add /= 10
            }
            
            //将两字符串相加
            let result:String = curr.reversed().map { String($0) }.joined()
            ans = addStrings(ans, result)
        }
        
        return ans
    }
    
    func addStrings(_ str1: String, _ str2: String) -> String {
        var i = str1.count - 1, j = str2.count - 1, add = 0
        
        var cur = [Int]()
        while i >= 0 || j >= 0 || add != 0 {
            
            let x = i>=0 ? Int(String(str1[str1.index(str1.startIndex, offsetBy: i)]))! : 0
            let y = j>=0 ? Int(String(str2[str2.index(str2.startIndex, offsetBy: j)]))! : 0
            
            let result = x + y + add
            
            cur.append(result % 10)
            add = result / 10
            
            i -= 1
            j -= 1
        }
        
        let result = cur.reversed().map { String($0) }.joined()
        return result
    }

OC

- (NSString *)multiply:(NSString *)num1 num2:(NSString *)num2 {
    
    if ([num1 isEqualToString:@"0"] || [num2 isEqualToString:@"0"]) {
        return @"0";
    }
    
    NSString *ans = @"";
    NSInteger m = num1.length;
    NSInteger n = num2.length;
    
    for (NSInteger i=n-1; i>=0; i--) {
        NSMutableArray *cur = @[].mutableCopy;
        NSInteger add = 0;//进位
        
        for (NSInteger j=n-1; j>i; j--) {
            [cur addObject:@(0)];
        }
        
        NSInteger x = [num2 characterAtIndex:i] - '0';
        
        for (NSInteger j=m-1; j>=0; j--) {
            NSInteger y = [num1 characterAtIndex:j] - '0';
            
            NSInteger result = x * y + add;
            
            [cur addObject:@(result%10)];
            add = result / 10;
        }
        
        while (add != 0) {
            [cur addObject:@(add%10)];
            add /= 10;
        }
        
        NSMutableString *str2 = @"".mutableCopy;
        [cur enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(NSNumber *obj, NSUInteger idx, BOOL * _Nonnull stop) {
            [str2 appendString:[NSString stringWithFormat:@"%d", [obj intValue]]];
        }];
        
        ans = [self addStrings:ans str2:str2];
    }
    return ans;
}


/// 两个字符串相加
/// - Parameters:
///   - str1: 字符串1
///   - str2: 字符串2
- (NSString *)addStrings:(NSString *)str1 str2:(NSString *)str2 {
    NSMutableArray *ans = @[].mutableCopy;
    NSInteger m = str1.length - 1, n = str2.length - 1, add = 0;
    
    while (m >= 0 || n >= 0 || add != 0) {
        NSInteger x = m >= 0 ? [str1 characterAtIndex:m] - '0' : 0;
        NSInteger y = n >= 0 ? [str2 characterAtIndex:n] - '0' : 0;
        
        NSInteger result = x + y + add;
        [ans addObject:@(result % 10)];
        add = result / 10;
        
        m--;
        n--;
    }
    
    NSMutableString *result = @"".mutableCopy;
    [ans enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(NSNumber *obj, NSUInteger idx, BOOL * _Nonnull stop) {
        [result appendString:[NSString stringWithFormat:@"%d", [obj intValue]]];
    }];
    return result;
}