資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學檢查子串是否可以透過替換 K 個字元來構成迴文串（針對 Q 個查詢）
引言
在本教程中，我們將實現一種方法來檢查子串是否可以透過替換 K 個字元來構成迴文串（針對 Q 個查詢）。迴文串是指正讀和反讀都相同的單詞。例如，“madam”、“refer”。
這裡，Q 個查詢是一個數值陣列，包含起始索引、結束索引和 K 的值。輸入字串的起始和結束索引值用於選擇位於這些起始和結束索引值之間的字元（兩個值都包含在內）。
對於這種方法，考慮一個字串 str，檢查其子串是否可以透過替換 K 個字元來構成迴文串。K 是為了使子串成為迴文串而替換的字元數。
示例 1
String s = "abcdef"
Queries = {{1, 4, 2}, {0, 4, 2}}
輸出
Yes Yes
解釋
在上面的例子中，字串是 "abcd"。
**查詢 1** − [1, 4, 1]，起始索引為 1，結束索引為 4，最多可以替換的字元數最多為 2 個。範圍 {1, 4} 內的子串是 "bcde"。
透過替換 1 個字元，它可以成為一個迴文串，迴文串是 "bcdd"。
**查詢 2** − [0, 4, 3]，起始索引為 0，結束索引為 4，最多可以替換 2 個字元以使子串成為迴文串。範圍 {0, 4} 內的子串是 "abcde"。
是的，透過替換 2 個字元，它可以成為一個迴文串，該回文串是 "abcba"。
示例 2
String s = "hello"
Queries = { { 1, 4, 0 }, {1, 4, 2 }, { 7, 10, 3 }};
輸出
No Yes Yes
解釋
輸入字串是 "helloindia"
**查詢 − {1, 4, 0}** − 起始索引為 1，結束索引為 4，最多可以替換 0 個字元以使子串成為迴文串。範圍 {1, 4} 內的子串是 "ello"。
否，透過替換 0 個字元，它不能成為迴文串。
**查詢 − {1, 4, 2}** − 起始索引為 1，結束索引為 4，最多可以替換 2 個字元以使子串成為迴文串。範圍 {1, 4} 內的子串是 "ello"。
是的，透過替換 2 個字元，它可以成為一個迴文串。替換 2 個字元後的迴文串是 "elle"。
**查詢 − {7, 10, 3}** − 起始索引為 7，結束索引為 10，最多可以替換 3 個字元以使子串成為迴文串。範圍 {7, 10} 內的子串是 "india"。
是的，它可以透過替換字元來構成迴文串。替換 2 個字元後的迴文串是 "indni"。
語法
**length()** − 這是在 `
` 標頭檔案中定義的字串類庫函式。它返回字串的長度。字串的長度是字串的字元數。
string_name.length();
**vector** − 它是 C++ 中用於儲存元素的容器。它是一個動態陣列，不受陣列大小限制。它可以是不同資料型別。
vector<data_type> vector_name;
**vector
vector<vector<data_type> > vector_name;
演算法
初始化字串 s。
使用數值陣列初始化查詢。
使用迴圈迭代字串字元。
建立一個二維向量，用於儲存使用查詢的起始和結束索引值生成的子串。
使用子串處理查詢並計算不匹配的字元數。
將一半的不匹配字元與剩餘字元轉換。
如果更改的字元數等於或小於 k 的值，則輸出為“Yes”。
如果替換的字元數大於 K 的值，則輸出“No”。
處理所有查詢。
示例 1
我們使用 C++ 中的動態規劃實現了其中一個演示。動態規劃降低了時間複雜度，並且不會多次執行相同的步驟。它將任務分成多個部分並使用遞迴。
#include <bits/stdc++.h>
using namespace std;
//User-defined function to find the palindromic strings from the generated substring
void findPalindrome(string s, vector<vector<int> >& Q){
int l = s.length();
vector<vector<int> > dpa(26, vector<int>(l, 0)); // 2d array to store the character count
//iterating the string to generate the substring
for (int x = 0; x < 26; x++) {
char currentCharVal= x + 'a'; // value of current character
for (int y = 0; y < l; y++) {
// Updating the dp array with new values of counter characters
if (y == 0) {
dpa[x][y] = (s[y] == currentCharVal); }
else {
dpa[x][y] = dpa[x][y - 1] + (s[y] == currentCharVal);
}
}
}
// Processing queries
for (auto query : Q) {
int leftInd = query[0];
int rightInd = query[1];
int k = query[2];
int unMatched = 0; // Find and storing the unmatched characters
for (int x = 0; x < 26; x++){
int cnt = dpa[x][rightInd] - dpa[x][leftInd] + (s[leftInd] == (x + 'a'));
if (cnt & 1)
unMatched++;
}
int result = unMatched / 2; // Initializing the value of result variable
// defining the condition for the Output
if (result <= k) {cout << "YES\n"; }
else {cout << "NO\n"; }
}
}
int main() {
string s = "helloindia";
vector<vector<int> > Q; // Initializing queries
Q = { { 1, 4, 0 }, {1, 4, 2 }, { 6, 9, 2 }, { 3, 8, 4 }};
// calling the function for processing the queries and generating substring
findPalindrome(s, Q);
return 0;
}
輸出
NO YES YES YES
示例 2
我們可以在本教程中無需動態規劃即可實現問題陳述。對於生成子串和處理查詢，使用了迴圈。使用變數“changes”計算已更改的字元數。當更改計數小於或等於 K 時，輸出為“Yes”，否則輸出為“No”。
使用 auto 自動定義變數的資料型別。
#include <iostream>
#include <vector>
using namespace std;
// Function to generate the substring and process the queries to check substring can be palindrome or not
void checkPalindrome(string s, vector<vector<int>>& Q) {
//processing queries
for (auto query : Q) {
int leftVal = query[0];
int rightVal = query[1];
int k = query[2];
int l = rightVal - leftVal + 1;
int unmatchedCnt = 0;
//vector to store values of characters
vector<int> cnt(26, 0);
//generating substring
for (int x = leftVal; x <= rightVal; x++)
cnt[s[x] - 'a']++;
for (int x = 0; x < 26; x++) {
if (cnt[x] % 2 != 0)
unmatchedCnt++;
}
int changes = unmatchedCnt / 2;
// condition for the Output
if (changes <= k)
cout << "YES\n";
else{
cout << "NO\n";
}
}
}
//Code Controller
int main() {
string s = "helloindia";
vector<vector<int>> Q = { { 1, 4, 0 }, {1, 4, 2 }, { 6, 9, 2 }, { 3, 8, 4 }};
checkPalindrome(s, Q);
return 0;
}
輸出
NO YES YES YES
結論
我們已經完成了本教程。在本教程中，我們考慮一個字串，並透過查詢生成子串。我們檢查子串是否可以透過替換最多 K 個字元來構成迴文串。K 是將子串轉換為迴文串而替換的最大字元數。為了在 C++ 中實現該任務，我們使用了迴圈和動態規劃。在本教程中，我們使用二維向量來儲存查詢。
163 次瀏覽
