資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律在 C++ 中查詢索引 i，使得 S1 的字首和 S2 到 i 的字尾連線後形成迴文串
概念
對於給定的兩個長度相等的字串 S1 和 S2，我們的任務是確定一個索引 i，使得 S1[0…i] 和 S2[i+1…n-1] 連線後形成迴文串。如果無法確定這樣的索引，則列印 -1。
輸入
S1 = “pqrsu”, S2 = “wxyqp”
輸出
1
S1[0..1] = “pq”，S2[2..n-1] = “ypq”
S1 + S2 = “pqyqp” 表示是一個迴文串。
輸入
S1 = “pqrst”, S2 = “qprqz”
輸出
-1
方法
- 首先，我們從 0 迭代到 n（字串的長度），並將 S1 中的第 i 個字元複製到另一個字串（假設為 S）。
- 然後我們取另一個臨時字串 temp，並將 S2 中從索引 i +1 到 n 的字元複製到 temp 中。
- 最後，我們驗證字串（S + temp）是否為迴文串。
示例
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Shows function that returns true if s is palindrome
bool isPalindrome(string str){
int i = 0;
int b = str.length() - 1;
while (i< b) {
if (str[i] != str[b])
return false;
i++;
b--;
}
return true;
}
// Shows function to return the required index
int getIndex1(string S1, string S2, int n){
string S = "";
for (int i = 0; i< n; a++) {
// Used to copy the ith character in S
S = S + S1[i];
string temp = "";
// Used to copy all the character of string s2 in Temp
for (int b = i + 1; b < n; b++)
temp += S2[b];
// Verify whether the string is palindrome
if (isPalindrome(S + temp)) {
return i;
}
}
return -1;
}
// Driver code
int main(){
string S1 = "pqrsu", S2 = "wxyqp";
int n = S1.length();
cout << getIndex1(S1, S2, n);
return 0;
}輸出
1
更新於: 2020-07-24
127 次檢視
廣告