แปลง String หนึ่งเป็นอีก String ด้วย Append และ Delete Last ใน C++

โจทย์ปัญหา

ได้รับ String สองตัว str1, str2 และจำนวน Operations k ตัดสินใจได้ไหมว่าแปลง str1 → str2 ด้วย Operation ทั้งหมด ก็อตเทอรี่ k ครั้ง โดย Operation มี 2 แบบ:

1. Append - เพิ่มตัวอักษรท้าย String
2. Delete Last - ลบตัวอักษรท้าย String

ตัวอย่าง

Input: str1 = "tutorials", str2 = "point", k = 5
Output: No

แนวคิดการแก้ปัญหา

1. หา Common Prefix Length (commonLen) ของ str1 และ str2
2. Operations ขั้นต่ำที่ต้องใช้ = (len1 - commonLen) + (len2 - commonLen) = len1 + len2 - 2*commonLen
   • Delete จาก str1 จนเหลือ Common Prefix: len1 - commonLen
   • Append เพื่อสร้าง str2 จาก Common Prefix: len2 - commonLen
3. เงื่อนไขสำคัญ: k ต้อง ≥ Min Operations และ (k - MinOps) ต้องเป็นเลขคู่
   • เพราะ Operation เหลือ (k - MinOps) ต้องทำเป็นคู่ Delete+Append (Net effect = 0)
4. กรณีพิเศษ: ถ้า k >= len1 + len2 → ทำได้เสมอ (ลบทั้งหมดแล้วสร้างใหม่ + เหลือ Operations ทำคู่กัน)

โค้ดตัวอย่าง (C++)

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

bool canConvert(string str1, string str2, int k) {
    int len1 = str1.length(), len2 = str2.length();

    // Special case: k มากพอที่จะลบทั้งหมดและสร้างใหม่
    if (k >= len1 + len2) return true;

    // หา Common Prefix
    int commonLen = 0;
    for (int i = 0; i < min(len1, len2); i++) {
        if (str1[i] == str2[i]) commonLen++;
        else break;
    }

    int minOps = (len1 - commonLen) + (len2 - commonLen);

    // ต้องมี k >= minOps และ (k - minOps) เป็นคู่
    return (k >= minOps) && ((k - minOps) % 2 == 0);
}

int main() {
    string str1 = "tutorials", str2 = "point";
    int k = 5;
    cout << (canConvert(str1, str2, k) ? "Yes" : "No") << endl;  // No

    // Test cases
    cout << canConvert("aba", "aba", 7) << endl;    // Yes (k >= len1+len2)
    cout << canConvert("abc", "def", 6) << endl;    // Yes (delete 3, append 3)
    cout << canConvert("abc", "def", 5) << endl;    // No (min=6, k=5)
    cout << canConvert("hackerhappy", "hackerrank", 9) << endl; // Yes
    return 0;
}

ผลลัพธ์

No
1
1
0
1

คำอธิบายเพิ่มเติม

• เป็นโจทย์ HackerRank "Append and Delete"
• Key Insight: Operations เหลือต้องเป็นคู่ (Delete + Append) เพื่อไม่เปลี่ยน String
• Time: O(min(len1, len2)), Space: O(1)
• Edge Case: k มากมาย (>= len1+len2) ทำได้เสมอ