LeetCode Medium 題集合 (六)：字符串相乘、全排列

1. Multiply Strings — 大數乘法

兩非負整數字符串相乘，返回積字符串。模擬豎式乘法：

1. 反轉兩字符串，低位在前
2. 雙循環逐位相乘，結果累加到 mid[i+j]
3. 統一處理進位
4. 反轉結果，去除前導零

string multiply(string num1, string num2) {
    if (num1=="0" || num2=="0") return "0";
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    vector mid(num1.size() + num2.size(), 0);
    for (int i=0; i= 10) {
            mid[i+1] += mid[i] / 10;
            mid[i] %= 10;
        }
    }
    while (mid.size()>1 && mid.back()==0) mid.pop_back();
    string res;
    for (int i=mid.size()-1; i>=0; --i) res.push_back('0'+mid[i]);
    return res;
}

2. Permutations — 全排列生成

利用 next_permutation 字典序生成：

1. 先 sort 得到最小排列
2. 循環調用 next_permutation 直到返回 false

bool nextPermutation(vector& nums) {
    int i = nums.size()-2;
    while (i>=0 && nums[i] >= nums[i+1]) --i;
    if (i < 0) return false;
    int j = nums.size()-1;
    while (nums[j] <= nums[i]) --j;
    swap(nums[i], nums[j]);
    reverse(nums.begin()+i+1, nums.end());
    return true;
}

vector> permute(vector& nums) {
    sort(nums.begin(), nums.end());
    vector> res;
    do { res.push_back(nums); } while (nextPermutation(nums));
    return res;
}

此法自動處理 Permutations II（含重複元素），因 next_permutation 基於字典序去重。

複雜度

• Multiply Strings：O(m·n) 時間，O(m+n) 空間
• Permutations：O(n!·n) 時間（輸出大小），O(n) 額外空間