C#で文字列内の指定した文字までの最短距離を求める方法

文字列 s と特定の文字 c が与えられたとき、s 内の各文字について、もっとも近い c までの距離を求めるのがこの問題です。ここでは、C# を使ってこの問題を線形時間で解くアルゴリズムをわかりやすく解説します。

アルゴリズムの考え方

ポイントは、leftDis と rightDis という役割の異なる 2 つの配列を用意することです。

• leftDis：左から右へ走査したときの、左側にある文字 c までの距離を格納します。
• rightDis：右から左へ走査したときの、右側にある文字 c までの距離を格納します。

走査中に文字 c に到達したら、その位置の距離を 0 として配列に記録し、その後の位置では距離を 1 ずつ加算していきます。すべての走査が完了したら、同じインデックス同士で 2 つの配列を比較し、小さい方の値を最終的な答えとして採用します。

時間計算量：O(n)
空間計算量：O(n)

実装例

public class Arrays
{
    public int[] ShortestDistanceToCharacter(string s, char c)
    {
        int stringLength = s.Length;
        int[] leftDis = new int[s.Length];
        int[] rightDis = new int[s.Length];

        leftDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray();
        rightDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray();

        // 左から右へ走査し、左側の文字 c からの距離を記録
        int count = int.MaxValue;
        for (int i = 0; i < rightDis.Length; i++)
        {
            if (s[i] == c)
            {
                count = 0;
                rightDis[i] = count;
            }
            else if (count != int.MaxValue)
            {
                count++;
                rightDis[i] = count;
            }
        }

        // 右から左へ走査し、右側の文字 c からの距離を記録
        count = int.MaxValue;
        for (int i = leftDis.Length - 1; i >= 0; i--)
        {
            if (s[i] == c)
            {
                count = 0;
                leftDis[i] = count;
            }
            else if (count != int.MaxValue)
            {
                count++;
                leftDis[i] = count;
            }
        }

        // 両方向の距離のうち、小さい方を採用
        int[] ans = new int[stringLength];
        for (int i = 0; i < stringLength; i++)
        {
            ans[i] = Math.Min(leftDis[i], rightDis[i]);
        }
        return ans;
    }
}

static void Main(string[] args)
{
    Arrays s = new Arrays();
    string ss = "lovecode";
    char c = 'e';
    var res = s.ShortestDistanceToCharacter(ss, c);
    foreach (var item in res)
    {
        Console.WriteLine(item);
    }
}

出力結果

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

文字列 "lovecode" の場合、文字 'e' はインデックス 3 と 7 の位置に存在します。たとえば先頭の 'l'（インデックス 0）からもっとも近い 'e' はインデックス 3 にあるため、距離は 3 となります。同様にして各位置の距離を計算すると、上記の配列が得られます。

ポイントまとめ

• 左右 2 方向からの走査を組み合わせることで、各位置の最近接文字までの距離を O(n) で効率的に求められます。
• 配列の初期値を int.MaxValue にしておくことで、まだ対応する文字が見つかっていない位置を正しく判定できます。
• 最終的な答えは、leftDis と rightDis の要素ごとの最小値です。