資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在C++中建立單詞（或字串）陣列中的迴文對
“Madam”或“racecar”是兩個正反讀都一樣的單詞，稱為迴文。
如果給定一個字串集合或列表，我們需要編寫一個C++程式碼來找出是否可以將列表中的任意兩個字串連線在一起形成迴文。如果給定列表中存在這樣的字串對，則需要列印“Yes”，否則需要列印“No”。
在本教程中，輸入將是一個字串陣列，輸出將是相應的字串值，例如
輸入
list[] = {"flat", "tea", "chair", "ptalf", "tea"}輸出
Yes
存在一對“flat”和“ptalf”，它們構成迴文字串“flatptalf”。
輸入
list[] = {"raman", "ram", "na", "ar", "man"}輸出
Yes
存在一對“na”和“man”，它們構成迴文字串“naman”。
查詢解決方案的方法
暴力法
對於陣列中的每個字串，檢查所有其他字串是否與任何其他字串一起形成迴文。如果找到這樣的對，則返回true。如果遍歷了所有陣列元素來搜尋這樣的對，並且沒有找到合適的對，則返回false。
時間複雜度：O(N^2)
空間複雜度：O(1)
示例
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome (string str) {
int len = str.length ();
for (int i = 0; i < len / 2; i++)
if (str[i] != str[len - i - 1])
return false;
return true;
}
bool checkPalindromePair (vector < string > vect) {
for (int i = 0; i < vect.size () - 1; i++) {
for (int j = i + 1; j < vect.size (); j++) {
string check_str = "";
check_str = check_str + vect[i] + vect[j];
if (isPalindrome (check_str))
return true;
}
}
return false;
}
int main () {
vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
return 0;
}輸出
Yes
高效或最佳化的方案
我們可以使用Trie資料結構來解決這個問題。
首先，我們需要建立一個空的Trie，對於陣列中的每個字串，我們需要插入當前單詞的反向，並存儲它是迴文到哪個索引。然後，我們需要再次遍歷陣列，對於每個字串，我們需要執行以下操作：
如果它在True中可用，則返回true
如果它部分可用——檢查剩餘的單詞是否是迴文。如果是，則返回true，這意味著一個對形成了迴文。
時間複雜度：O(Nk^2)
空間複雜度：O(N)
其中N是列表中的單詞數，k是檢查迴文的最大長度。
示例2
#include<bits/stdc++.h>
using namespace std;
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
struct TrieNode {
struct TrieNode *children[ALPHABET_SIZE];
vector < int >pos;
int id;
bool isLeaf;
};
struct TrieNode *
getNode (void) {
struct TrieNode *pNode = new TrieNode;
pNode->isLeaf = false;
for (int i = 0; i < ALPHABET_SIZE; i++)
pNode->children[i] = NULL;
return pNode;
}
bool isPalindrome (string str, int i, int len) {
while (i < len) {
if (str[i] != str[len])
return false;
i++, len--;
}
return true;
}
void insert (struct TrieNode *root, string key, int id) {
struct TrieNode *pCrawl = root;
for (int level = key.length () - 1; level >= 0; level--) {
int index = CHAR_TO_INDEX (key[level]);
if (!pCrawl->children[index])
pCrawl->children[index] = getNode ();
if (isPalindrome (key, 0, level))
(pCrawl->pos).push_back (id);
pCrawl = pCrawl->children[index];
}
pCrawl->id = id; pCrawl->pos.push_back (id);
pCrawl->isLeaf = true;
}
void
search (struct TrieNode *root, string key, int id,
vector < vector < int > >&result) {
struct TrieNode *pCrawl = root;
for (int level = 0; level < key.length (); level++) {
int index = CHAR_TO_INDEX (key[level]);
if (pCrawl->id >= 0 && pCrawl->id != id && isPalindrome (key, level, key.size () - 1)) result.push_back ( { id, pCrawl->id} );
if (!pCrawl->children[index]) return; pCrawl = pCrawl->children[index];
}
for (int i:pCrawl->pos) {
if (i == id) continue;
result.push_back ( { id, i} );
}
}
bool checkPalindromePair (vector < string > vect) {
struct TrieNode *root = getNode ();
for (int i = 0; i < vect.size (); i++)
insert (root, vect[i], i);
vector < vector < int >>result;
for (int i = 0; i < vect.size (); i++) {
search (root, vect[i], i, result);
if (result.size () > 0) return true;
}
return false;
}
// Driver code int main () {
vector < string > vect = { "flat", "tea", "chair", "ptalf", "tea"};
checkPalindromePair (vect) ? cout << "Yes" : cout << "No";
return 0;
}輸出
Yes
結論
在本教程中，我們學習瞭如何使用兩種方法（暴力法和最佳化方法）在陣列中查找回文對。我們也可以用Java、Python和其他語言編寫這段程式碼。第一種方法是透過遍歷所有給定元素來查詢任何解決方案的基本方法。相比之下，第二種方法使用Trie資料結構，因此它可以在幾乎線性的時間複雜度內給出答案。我們希望您覺得本教程有所幫助。
更新於：2022年3月7日
450 次瀏覽
廣告