समस्या विवरण
मान लीजिए हमारे पास एक लोअरकेस स्ट्रिंग s है, हमें इसे कम से कम स्ट्रिंग्स में विभाजित करना है ताकि प्रत्येक स्ट्रिंग एक पालिंड्रोम हो, और फिर स्ट्रिंग्स की संख्या ज्ञात करनी है।
उदाहरण के लिए, यदि इनपुट है s = "levelracecar", तो आउटपुट 2 होगा, क्योंकि दो पालिंड्रोम "level" और "racecar" हैं।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- n := स्ट्रिंग A का आकार
- आकार n+1 का एक ऐरे result परिभाषित करें
- result[n] := -1
- i := n-1 से 0 तक (घटते क्रम में):
- result[i] := n - i - 1
- j := i से n-1 तक:
- यदि A का सबस्ट्रिंग i से j तक पालिंड्रोम है, तो result[i] := min(result[i], 1 + result[j+1])
- result[0] + 1 वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isPalindrome(string A) {
int left = 0;
int right = A.size() - 1;
while (left < right) {
if (A[left] != A[right]) return 0;
left++;
right--;
}
return 1;
}
int solve(string A) {
int n = A.size();
vector<int> result(n + 1);
result[n] = -1;
for (int i = n - 1; i >= 0; i--) {
result[i] = n - i - 1;
for (int j = i; j < n; j++) {
if (isPalindrome(A.substr(i, j - i + 1))) {
result[i] = min(result[i], 1 + result[j + 1]);
}
}
}
return result[0] + 1;
}
};
int solve(string s) {
return (new Solution())->solve(s);
}
int main() {
string s = "levelracecar";
cout << solve(s);
}
इनपुट
"levelracecar"
आउटपुट
2
