ตรวจสอบเซลล์ในสตริงว่าถูกเยี่ยมชมซ้ำได้หรือไม่ใน C++

ปัญหา

ให้สตริงที่ประกอบด้วย '.' (เซลล์ว่าง) และตัวเลข (0-9) ตัวเลข x หมายถึงสามารถเคลื่อนที่ซ้ายหรือขวา x ก้าวได้ ตรวจสอบว่ามีเซลล์ไหนถูกเยี่ยมชมได้มากกว่า 1 วิธีหรือไม่

ตัวอย่าง: ".2...2.." (index: 0 1 2 3 4 5 6 7)

• Index 1 (ค่า 2): ไปได้ index 3 (ขวา 2) หรือ index -1 (ซ้าย 2, invalid)
• Index 5 (ค่า 2): ไปได้ index 3 (ซ้าย 2) หรือ index 7 (ขวา 2)
• Index 3 ถูกเยี่ยมชมได้ 2 วิธี (จาก 1 และ 5) → YES

อัลกอริทึม

1. สร้างอาร์เรย์ visited[n] = 0
2. วน i = 0 ถึง n-1:
   • ถ้า str[i] เป็นตัวเลข x:
   • สำหรับ j = max(0, i-x) ถึง min(n-1, i+x): visited[j]++
3. ตรวจสอบ visited มีค่า ≥ 2 ไหม

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool hasRevisitableCell(const string& str) {
    int n = str.length();
    vector visited(n, 0);
    
    for (int i = 0; i < n; i++) {
        if (isdigit(str[i])) {
            int x = str[i] - '0';
            int left = max(0, i - x);
            int right = min(n - 1, i + x);
            
            for (int j = left; j <= right; j++) {
                visited[j]++;
            }
        }
    }
    
    for (int v : visited) {
        if (v >= 2) return true;
    }
    return false;
}

int main() {
    string tests[] = {
        ".2...2..",   // YES (index 3 visited twice)
        "1.1.1",      // YES (index 1 visited from 0 and 2)
        "..1..",      // NO (only index 2 can move)
        "9.........", // YES (index 0 can reach many)
        "........."   // NO (no numbers)
    };
    
    for (const string& s : tests) {
        cout << s << ": " << (hasRevisitableCell(s) ? "YES" : "NO") << endl;
    }
    return 0;
}

ผลลัพธ์

.2...2..: YES
1.1.1: YES
..1..: NO
9.........: YES
.........: NO

ความซับซ้อน

• เวลา: O(n × max_digit) ≤ O(10n) = O(n)
• พื้นที่: O(n)

การปรับปรุง

ใช้ Difference Array (Prefix Sum technique) ลดเป็น O(n):

vector diff(n + 1, 0);
for (int i = 0; i < n; i++) {
    if (isdigit(str[i])) {
        int x = str[i] - '0';
        int l = max(0, i - x);
        int r = min(n - 1, i + x);
        diff[l]++; 
        diff[r + 1]--;
    }
}
// Prefix sum
int curr = 0;
for (int i = 0; i < n; i++) {
    curr += diff[i];
    if (curr >= 2) return true;
}
return false;