【C++】文字列内の各文字から指定した文字までの最短距離を求める方法

文字列 a と特定の文字 char が与えられたとき、文字列内の各文字から char までの距離を出力するのが本記事のテーマです。出力する距離配列のサイズは元の文字列と同じになります。これは、文字列内のすべての文字について、対象となる文字までの距離を求める必要があるためです。

入力例と出力例

例1

a = "tutorialspoint"
char = "o"

出力：

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

この文字列では「o」はインデックス3とインデックス10の2箇所に存在します。各位置から最も近い「o」までの距離を計算すると、上記のような配列が得られます。

例2

a = "programmer"
char = "r"

出力：

[1, 0, 1, 1, 0, 1, 2, 2, 1, 0]

「r」はインデックス1、4、9に出現するため、文字列内の各文字からの最短距離は上記の配列となります。

問題を解くためのアプローチ

この問題に対する最もシンプルな解法（全探索）は、まず文字列内における指定文字の出現位置をすべて配列に記録し、その後、文字列全体を走査しながら各位置と出現位置との距離の最小値を求める方法です。

• 文字列と文字 char を入力として受け取ります。
• 関数 shortestToChar(string a, char ch) は、文字列と文字を引数に取り、文字列内の各文字から指定文字までの距離を出力します。
• 文字列 a を走査し、指定文字が出現する位置をベクター（動的配列）に格納します。
• 続いて文字列と出現位置の配列を走査し、各文字から指定文字までの最小距離を計算します。
• 最後に、結果の距離配列を出力します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
void shortestToChar(string a, char C) {
    vector < int > 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);
}

上記のコードを実行すると、以下の出力が得られます。

出力

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

文字列「tutorialspoint」において、文字「o」はインデックス3とインデックス10に存在します。そのため、前後の各文字から最も近い「o」までの距離を計算すると、[3 2 1 0 1 2 3 3 2 1 0 1 2 3] という結果になります。

なお、この手法の時間計算量は O(n × k) です（n は文字列の長さ、k は指定文字の出現回数）。文字列が非常に長い場合は、左方向と右方向からの2回の走査で各位置の最短距離を求めることで、O(n) まで計算量を抑える最適化も可能です。