Chương trình C++ tìm khoảng cách ngắn nhất đến ký tự

Cho chuỗi 'a' và ký tự 'char', tìm khoảng cách từ 'char' đến mỗi ký tự trong chuỗi. Kết quả là mảng cùng độ dài chuỗi.

Ví dụ

a="tutorialspoint", char='o'

Output: [3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3]

a="programmer", char='r'

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

Cách tiếp cận: Brute Force

• Lưu vị trí ký tự char vào vector pos
• Duyệt chuỗi, với mỗi index i tính min(|pos[j] - i|)
• Lưu vào vector dist

Code C++

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

void shortestToChar(string a, char C) {
    vector pos, dist;
    for (int i = 0; i < a.size(); i++)
        if (a[i] == C) pos.push_back(i);
    for (int i = 0; i < a.size(); i++) {
        int mn = INT_MAX;
        for (int j = 0; j < pos.size(); j++)
            mn = min(mn, abs(pos[j] - i));
        dist.push_back(mn);
    }
    for (auto i : dist) cout << i << " ";
}

int main() {
    string a = "tutorialspoint";
    char ch = 'o';
    shortestToChar(a, ch);
}

Kết quả

3 2 1 0 1 2 3 3 2 1 0 1 2 3

'o' ở index 3 và 10. Khoảng cách gần nhất tính từ các vị trí này.