โปรแกรมคูณสตริงสองตัวและคืนผลลัพธ์เป็นสตริงใน C++

ภาพรวมปัญหา

ให้ตัวเลขสองตัวในรูปแบบสตริง ต้องการคูณกันและคืนผลลัพธ์เป็นสตริง (รองรับตัวเลขใหญ่เกิน range ของ built-in types)

ตัวอย่าง

Input: "28", "25"

Output: "700"

แนวทางแก้ปัญหา (Grade School Multiplication)

1. ผลคูณของตัวเลข m หลักและ n หลัก มีได้มากสุด m+n หลัก
2. สร้าง array ans[m+n] เริ่มต้น 0
3. คูณแต่ละคู่หลัก num1[i] × num2[j] บวกเข้า ans[i+j+1]
4. จัดการ carry: ans[i+j] += ans[i+j+1] / 10, ans[i+j+1] %= 10
5. ข้าม leading zeros แล้วแปลงเป็น string

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        int n = num1.size();
        int m = num2.size();
        string ans(n + m, '0');
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                int p = (num1[i] - '0') * (num2[j] - '0') + (ans[i + j + 1] - '0');
                ans[i + j + 1] = (p % 10) + '0';
                ans[i + j] += p / 10;
            }
        }
        
        // ข้าม leading zeros
        for (int i = 0; i < n + m; i++) {
            if (ans[i] != '0') return ans.substr(i);
        }
        return "0";
    }
};

int main() {
    Solution ob;
    cout << ob.multiply("28", "25");
    return 0;
}

ผลลัพธ์

"700"

การทำงานทีละขั้น (28 × 25)

    2 8
  × 2 5
  -----
    1 4 0  (28 × 5)
  5 6     (28 × 2, shift left)
  -----
  7 0 0

ในอาร์เรย์ ans (size 4): index 0,1,2,3

• i=1 (8), j=1 (5): p=40 → ans[3]=0, ans[2]+=4
• i=1 (8), j=0 (2): p=16+4=20 → ans[2]=0, ans[1]+=2
• i=0 (2), j=1 (5): p=10+2=12 → ans[2]=2, ans[1]+=1
• i=0 (2), j=0 (2): p=4+3=7 → ans[1]=7, ans[0]=0
• ผลลัพธ์: "0700" → skip leading zero → "700"

ข้อควรระวังในโค้ดต้นฉบับ

• คำอธิบายในโค้ดต้นฉบับผสมกับอัลกอริทึมหาร (Division algorithm) ไม่เกี่ยวข้องกับการคูณ
• การใช้ `ans[i+j] += p / 10` ถูกต้องเพราะ ans เก็บเป็น char '0'..'9' การบวก int เข้า char ทำงานได้เพราะ ASCII ต่อเนื่อง

ความซับซ้อน

• เวลา: O(N × M) — N, M = ความยาวสตริง
• พื้นที่: O(N + M)

ขยายประยุกต์

อัลกอริทึม Karatsuba (O(N^1.585)), FFT (O(N log N)) สำหรับตัวเลขใหญ่มาก (หลายพันหลัก)