Trong bài toán này, chúng ta được cho một chuỗi str và một số nguyên pow. Nhiệm vụ của chúng ta là tìm một chuỗi con với sức mạnh cho trước.
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 sức mạnh của các ký tự trong nó.
Sức mạnh ký tự: a -> 1, b -> 2, c -> 3,...
Hãy xem ví dụ sau để hiểu bài toán:
Input : string = "programming" power = 49 Output : 'pro'
Giải thích −
Sức mạnh chuỗi: pro, power(p) = 16 power(r) = 18 power(o) = 15 Tổng = 16 + 18 + 15 = 49
Phương pháp giải
Một giải pháp đơn giản là sử dụng vòng lặp lồng nhau. Ta lặp qua chuỗi và dùng vòng lặp trong để tìm chuỗi con. Với mỗi chuỗi con, tính sức mạnh và kiểm tra xem có bằng 'pow' hay không, trả về true nếu có, ngược lại false.
Một phương pháp hiệu quả hơn là sử dụng map để lưu sức mạnh. Ta tính sức mạnh chuỗi con và lưu vào map. Kiểm tra xem có giá trị nào trong map có thể làm sức mạnh bằng sức mạnh yêu cầu. Nếu có, trả về true. Trả về false khi duyệt hết chuỗi và không tìm thấy giá trị khớp sức mạnh.
Thuật toán
Bước 1 − Duyệt chuỗi và tìm sức mạnh (currPow).
Bước 2 − Kiểm tra xem giá trị (currPow - pow) có tồn tại trong map hay không.
Bước 2.1 − Nếu có, in -> chuỗi con.
Bước 3 − Chèn giá trị currPow vào map.
Bước 4 − Nếu duyệt hết ký tự chuỗi, in -> 'không thể'.
Ví dụ
Chương trình minh họa cho giải pháp
#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; }Kết quả
Substring : pro has power 49