นับจำนวนครั้งที่ Substring ปรากฏใน String แบบ Recursive ใน Java

กำหนดสตริงสองตัว str1 และ str2 ต้องการนับจำนวนครั้งที่ str2 ปรากฏใน str1 โดยใช้การเรียกฟังก์ชันตัวเอง (Recursion)

ตัวอย่าง

str1 = "TPisTPareTPamTP", str2 = "TP"
Output: 4

str1 = "HiHOwAReyouHiHi", str2 = "Hi"
Output: 3

แนวทางแก้ปัญหา: Recursive + contains() + replaceFirst()

1. ตรวจสอบว่า str1.contains(str2) เป็น true หรือไม่
2. ถ้า true: ใช้ str1.replaceFirst(str2, "") แทนที่ครั้งแรกด้วยสตริงว่าง แล้วเรียกฟังก์ชันซ้ำ + 1
3. ถ้า false: คืนค่า 0 (base case)

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

public class RecursiveSubstringCount {
    public static void main(String[] args) {
        String str1 = "TPisTPareTPamTP";
        String str2 = "TP";
        System.out.println("Count of occurrences of a substring recursively are: " 
            + countOccurrences(str1, str2));
    }

    static int countOccurrences(String str, String sub) {
        if (str.contains(sub)) {
            // แทนที่ครั้งแรก แล้วเรียกซ้ำ + 1
            return 1 + countOccurrences(str.replaceFirst(sub, ""), sub);
        }
        return 0; // base case: ไม่พบ substring แล้ว
    }
}

ผลลัพธ์

Count of occurrences of a substring recursively are: 4

การทำงานแบบขั้นตอน (Trace)

str="TPisTPareTPamTP", sub="TP"
1. contains("TP")=true → replaceFirst → "isTPareTPamTP" + count(1)
2. contains("TP")=true → replaceFirst → "isareTPamTP" + count(1)
3. contains("TP")=true → replaceFirst → "isareamTP" + count(1)
4. contains("TP")=true → replaceFirst → "isaream" + count(1)
5. contains("TP")=false → return 0
Total = 1+1+1+1+0 = 4

ข้อควรระวัง

• Stack Overflow: หาก substring ปรากฏมากเกินไป (เช่น > 10,000 ครั้ง) อาจเกิด StackOverflowError → ควรใช้ iterative แทน
• Overlapping: replaceFirst จับคู่แบบ non-overlapping (เช่น "aaa" หา "aa" จะได้ 1 ครั้ง ไม่ใช่ 2) → ถ้าต้องการ overlapping ต้องใช้ indexOf แทน
• Performance: สร้าง String ใหม่ทุกครั้ง → O(n²) time, O(n²) space

static int countOccurrencesIterative(String str, String sub) {
    int count = 0;
    int index = 0;
    while ((index = str.indexOf(sub, index)) != -1) {
        count++;
        index += sub.length(); // ข้ามไปหน้าครั้งที่เจอ (non-overlapping)
        // ถ้าต้องการ overlapping: index += 1;
    }
    return count;
}