資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式中檢查子串[L…R]是否為迴文
在這個問題中，我們給定一個字串str，Q個查詢，每個查詢包含兩個值L和R，用於子串[L...R]。我們的任務是建立一個程式來解決查詢，以檢查子串[L…R]是否為迴文。
問題描述 − 為了解決每個查詢，我們需要檢查L到R範圍內的子串是否為迴文。
讓我們舉個例子來理解這個問題：
輸入
str = “abccbeba” , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}}輸出
Palindrome Not Palindrome Palindrome
解釋
Creating all substring for the given substrings : Substring[1...4] = “bccb”, it is a palindrome Substring[0...6] = “abccbeb”, it is a not palindrome Substring[4...6] = “beb”, it is a palindrome
解決方案
解決這個問題的一個簡單方法是解決每個查詢。為此，我們需要找到從索引範圍L到R的子串。並檢查子串是否為迴文。
程式說明了我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
int i, length;
int flag = 0;
length = str.length();
for(i=0;i < length ;i++){
if(str[i] != str[length-i-1]) {
flag = 1; break;
}
}
if (flag==1)
return 1;
return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
for(int i = 0; i < Q; i++){ isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))?cout<<"Palindrome\n":cout<<"Not palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
}輸出
Palindrome Not palindrome! Palindrome
這是一個樸素的方法，但效率不高。
解決這個問題的一個有效方法是使用動態規劃方法。為了解決這個問題，我們需要建立一個DP陣列，一個二維陣列，儲存布林值，表示子串[i...j]是否為迴文，用於DP[i][j]。
我們將建立這個DP矩陣，並檢查每個查詢的所有L-R值。
程式說明了我們解決方案的工作原理：
示例
#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
int length = str.size();
int i, j;
for (i = 0; i < length; i++) {
for (j = 0; j < length; j++)
DP[i][j] = 0;
}
for (j = 1; j <= length; j++) {
for (i = 0; i <= length - j; i++) {
if (j <= 2) {
if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = 1;
}
else if (str[i] == str[i + j - 1])
DP[i][i + j - 1] = DP[i + 1][i + j - 2];
}
}
}
void solveAllQueries(string str, int Q, int query[][2]){
int DP[50][50];
computeDP(DP, str);
for(int i = 0; i < Q; i++){
DP[query[i][0] - 1][query[i][1] - 1]?cout<<"not palindrome!\n":cout<<"palindrome!\n";
}
}
int main() {
string str = "abccbeba"; int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
}輸出
palindrome! not palindrome! palindrome!
更新於：2020年12月22日
440 次瀏覽
廣告