ค้นหาสตริงย่อยที่มีพลังที่กำหนดใน 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' ให้คืนค่า จริง หากใช่ มิฉะนั้น ให้คืนค่าเท็จ

วิธีที่มีประสิทธิภาพในการแก้ปัญหาคือการใช้แผนที่เพื่อเก็บพลังงาน เราจะคำนวณพลังของสตริงย่อยและจัดเก็บไว้ในแผนที่ ตรวจสอบว่ามีค่าอยู่ในแผนที่ที่สามารถทำให้พลังเท่ากับพลังงานที่ต้องการหรือไม่ ถ้าใช่ ให้คืนค่า จริง . ส่งกลับ เท็จ เมื่ออักขระทั้งหมดของสตริงถูกข้ามไปและไม่พบค่าพลังที่ตรงกัน

อัลกอริทึม

• ขั้นตอนที่ 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