Tìm chuỗi con với sức mạnh đã cho trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi str và một số nguyên pow. Nhiệm vụ của chúng tôi là tìm một chuỗi con có sức mạnh cho trước .

Chúng ta cần trả về chuỗi con có sức mạnh bằng pow.

Sức mạnh của chuỗi là tổng quyền hạn của các ký tự của nó.

Sức mạnh của nhân vật:a -> 1, b -> 2, c -> 3, ...

Hãy lấy một ví dụ để hiểu vấn đề,

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

Giải thích -

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là sử dụng các vòng lặp lồng nhau. Chúng tôi sẽ lặp qua chuỗi và sử dụng một vòng lặp bên trong, chúng tôi sẽ tìm thấy chuỗi con. Đối với mỗi chuỗi con, chúng tôi sẽ tính toán công suất. Và sau đó kiểm tra xem nó có bằng 'pow' không, trả về true nếu có, nếu không thì trả về false.

Một cách tiếp cận hiệu quả để giải quyết vấn đề là sử dụng bản đồ để lưu trữ điện năng. Chúng tôi sẽ tính toán sức mạnh của chuỗi con và lưu trữ nó trên bản đồ. Kiểm tra xem một giá trị tồn tại trong bản đồ có thể làm cho công suất bằng với công suất yêu cầu hay không. Nếu có, hãy trả về true . Trả lại false khi tất cả các ký tự của chuỗi được duyệt và không tìm thấy giá trị khớp giá trị nào.

Thuật toán

• Bước 1 - Duyệt qua chuỗi và tìm công suất (currPow).

• Bước 2 - Nếu giá trị, (currPow - pow) có tồn tại trong bản đồ hay không.

  • Bước 2.1 - nếu có, hãy in -> chuỗi con.

• Bước 3 - Chèn giá trị của currPow vào bản đồ.

• Bước 4 - Nếu tất cả các ký tự của chuỗi được duyệt qua, hãy in -> "không thể thực hiện được".

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

Substring : pro has power 49