หา Shortest Distance ถึง Character ใน String C++

โจทย์

กำหนด String s และ Character c หา Array dist ที่ dist[i] = ระยะทางสั้นที่สุดจาก s[i] ไปยัง c ใกล้ที่สุด

ตัวอย่าง

s = "tutorialspoint", c = 'o'

Index ของ 'o': 3, 10

Index:  0  1  2  3  4  5  6  7  8  9  10 11 12 13
Char:   t  u  t  o  r  i  a  l  s  p  o  i  n  t
Dist:   3  2  1  0  1  2  3  3  2  1  0  1  2  3

แนวคิด: Two Pass (Forward + Backward)

1. Forward Pass: เก็บระยะจาก c ด้านซ้าย
2. Backward Pass: อัปเดตด้วยระยะจาก c ด้านขวา (ถ้าน้อยกว่า)

โค้ด C++

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

vector<int> shortestToChar(string s, char c) {
    int n = s.size();
    vector<int> dist(n, INT_MAX);
    
    // Forward Pass: ระยะจาก c ด้านซ้าย
    int prev = -1;
    for (int i = 0; i < n; i++) {
        if (s[i] == c) prev = i;
        if (prev != -1) dist[i] = i - prev;
    }
    
    // Backward Pass: ระยะจาก c ด้านขวา
    prev = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == c) prev = i;
        if (prev != -1) dist[i] = min(dist[i], prev - i);
    }
    
    return dist;
}

int main() {
    string s = "tutorialspoint";
    char c = 'o';
    
    vector<int> result = shortestToChar(s, c);
    
    cout << "[";
    for (size_t i = 0; i < result.size(); i++) {
        cout << result[i] << (i + 1 < result.size() ? ", " : "");
    }
    cout << "]" << endl;
    
    // Test case 2
    string s2 = "programmer";
    char c2 = 'r';
    auto r2 = shortestToChar(s2, c2);
    for (int x : r2) cout << x << " ";
    cout << endl;
    
    return 0;
}

วิธีอื่น: เก็บ Index ของ c ก่อน

vector<int> shortestToCharV2(string s, char c) {
    vector<int> positions;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == c) positions.push_back(i);
    }
    
    vector<int> dist(s.size());
    for (int i = 0; i < s.size(); i++) {
        int mn = INT_MAX;
        for (int pos : positions) {
            mn = min(mn, abs(pos - i));
        }
        dist[i] = mn;
    }
    return dist;
}

Complexity

k = จำนวนครั้งที่ c ปรากฏ (Two Pass ดีที่สุด)

ผลลัพธ์

[3, 2, 1, 0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3]
1 0 1 2 0 1 2 3 4 0

สรุป

Shortest Distance to Character แก้ได้ O(n) ด้วย Two Pass (Forward/Backward) เก็บระยะจาก Target Char ด้านซ้ายและขวา แล้วเอา Min - LeetCode 821