文字までの最短距離を見つけるためのC++プログラム

文字列'a'と文字'char'が与えられた場合、タスクは、与えられた文字列の各文字からの'char'の距離を出力することです。距離配列のサイズは、指定された文字列の各文字からの文字の距離を見つける必要があるため、文字列のサイズと同じです。

例

入力-1：

a = “tutorialspoint”
char = “o”

出力：

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

説明： 指定された文字列では、指定された文字列の各文字からの文字の距離は[3、2、1、0、1、2、3、4、5、6、0、1、2、3]です。

入力-2：

a = “programmer”
char = “r”

出力：

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

説明： 指定された文字列では、指定された文字列の各文字からの「r」の距離は[1、0、1、2、0、1、2、3、4、0]です。

この問題を解決するためのアプローチ

この問題を解決するためのブルートフォースアプローチは、文字列内の指定された文字の位置を見つけて、配列に格納することです。次に、文字列全体と位置配列を繰り返し処理して、指定された文字列内の文字の最小距離を見つけます。

• 文字列と文字「char」を入力として使用します。
• 関数distanceTochar（string a、char ch）は、文字列と文字を入力として受け取り、指定された文字列の各文字から指定された文字までの距離を出力します。
• 文字列'a'を反復処理し、指定された文字の位置をベクトルに格納します。
• 次に、文字列と位置の配列を繰り返し処理し、文字列内の文字の距離を計算します。
• 位置配列を印刷します。

例

#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に存在します。したがって、前後の文字からの最も近い距離を計算すると、距離は[3 2 1 012として取得されます。 3 3 2 1 0 123]。