"Madam" 또는 "racecar"는 회문이라고 하는 앞으로 읽는 것과 뒤로 읽는 것이 같은 두 단어입니다.
문자열 모음이나 목록이 주어지면 목록의 두 문자열을 결합하여 회문을 형성할 수 있는지 알아보기 위해 C++ 코드를 작성해야 합니다. 주어진 목록에 그러한 문자열 쌍이 있으면 "예"를 인쇄해야 하고, 그렇지 않으면 "아니오"를 인쇄해야 합니다.
이 자습서에서 입력은 문자열 배열이 되고 출력은 그에 따라 문자열 값이 됩니다. 예를 들어
입력
list[] = {"flat", "tea", "chair", "ptalf", "tea"} 출력
Yes
회문 문자열 "flatptalf"를 형성하는 "flat" 및 "ptalf" 쌍이 있습니다.
입력
list[] = {"raman", "ram", "na", "ar", "man"} 출력
Yes
회문 문자열 "naman"을 형성하는 "na"와 "man" 쌍이 있습니다.
해결책을 찾기 위한 접근 방식
무차별 대입 접근
배열의 각 문자열에 대해 다른 모든 문자열과 회문을 형성하는지 여부를 확인합니다. 그러한 쌍이 발견되면 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
효율적이거나 최적화된 접근 방식
이 문제를 해결하기 위해 tri 데이터 구조를 사용할 수 있습니다.
먼저 빈 트라이를 만들고 배열의 각 문자열에 대해 현재 단어의 역순을 삽입하고 어느 인덱스까지 회문인지 저장해야 합니다. 그런 다음 배열을 다시 탐색해야 하며 각 문자열에 대해 다음을 수행해야 합니다.
-
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
결론
이 자습서에서는 두 가지 접근 방식(Bruteforce 및 Optimized)을 사용하여 배열에서 회문 쌍을 찾는 방법을 배웠습니다. 우리는 또한 자바, 파이썬 및 기타 언어로 이 코드를 작성할 수 있습니다. 첫 번째 접근 방식은 주어진 모든 요소를 순회하여 솔루션을 찾는 기본적인 방법입니다. 대조적으로, 두 번째 접근 방식은 tri 데이터 구조를 사용하므로 답은 거의 선형 시간 복잡도입니다. 이 튜토리얼이 도움이 되기를 바랍니다.