C++で与えられた力を持つ部分文字列を見つける

この問題では、文字列strと整数powが与えられます。私たちの仕事は、与えられた力を持つサブストリングを見つけることです 。

パワーがpowに等しいサブストリングを返す必要があります。

文字列の力 はそのキャラクターの力の合計です。

キャラクターの力：a-> 1、b-> 2、c-> 3、...

問題を理解するために例を見てみましょう

Input : string = "programming" power = 49
Output : 'pro'

説明 −

Power of matrix : pro,
power(p) = 16
power(p) = 18
power(p) = 15
Total = 16 + 18 + 15 = 49

ソリューションアプローチ

この問題の簡単な解決策は、ネストされたループを使用することです。文字列をループし、内部ループを使用してサブ文字列を見つけます。サブストリングごとに、パワーを計算します。次に、それが「pow」と等しいかどうかを確認し、等しい場合はtrueを返し、そうでない場合はfalseを返します。

この問題を解決するための効率的なアプローチは、マップを使用して電力を蓄えることです。サブストリングの累乗を計算し、マップに保存します。電力を必要な電力と等しくすることができる値がマップに存在するかどうかを確認します。はいの場合、 trueを返します 。 falseを返します 文字列のすべての文字がトラバースされ、値に一致するパワーが見つからない場合。

アルゴリズム

• ステップ1 −文字列をトラバースして、パワー（currPow）を見つけます。

• ステップ2 −値（currPow --pow）がマップに存在するかどうか。

  • ステップ2.1 −はいの場合、印刷->部分文字列。

• ステップ3 −currPowの値をマップに挿入します。

• ステップ4 −文字列のすべての文字をトラバースする場合は、->「不可能」と出力します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
void findSubStringWithPower(string str, int power) {
   int i;
   unordered_map<int , int > powerSS;
   int currPower = 0;
   int N = str.length();
   for (i = 0; i < N; i++) {
      currPower = currPower + (str[i] - 'a' + 1);
      if (currPower == power) {
         cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power;
         return;
      }
      if (powerSS.find(currPower - power) != powerSS.end()) {
         cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1);
         cout<<" has power "<<power; return;
      }
      powerSS[currPower] = i;
   }
   cout<<"No substring found!";
}
int main() {
   string str = "programming";
   int power = 49;
   findSubStringWithPower(str, power);
   return 0;
}

出力

Substring : pro has power 49