https://leetcode.com/problems/palindrome-partitioning/description/
문자열이 주어질 때, palindrome한 sub string의 모음을 찾아라.
BackTrack의 원리 자체는 같지만, 구성과 진행 조건이 조금 다르다.
실제로 string을 cut 해 보며 이것이 palindrome인지 확인하고, 그럴 때만 진행해 나간다.
나머지 조건은 대동소이 하다.
코드
더보기
bool IsPalindrome(const string& s)
{
if (s.size() <= 1)
return true;
int mid = s.size() / 2;
for (int q = 0; q < mid; ++q)
{
if (s[q] != s[s.size() - q - 1])
return false;
}
return true;
}
void partitionBT(vector<vector<string>>& vRet, vector<string>& vCur, const string& s, int idx)
{
if (idx >= s.size())
{
vRet.push_back(vCur);
return;
}
for (int q = idx; q < s.size(); ++q)
{
string cur = s.substr(idx, q-idx+1);
if (IsPalindrome(cur))
{
// cout << cur << endl;
vCur.push_back(cur);
partitionBT(vRet, vCur, s, q+1);
vCur.pop_back();
}
}
}
vector<vector<string>> partition(string s)
{
vector<vector<string>> vRet;
vector<string> vCur;
partitionBT(vRet, vCur, s, 0);
return vRet;
}
결과
'Leetcode > NeetCode' 카테고리의 다른 글
[BackTrack][Hard] 51. N-Queens (0) | 2024.07.31 |
---|---|
[BackTrack][Medium] 17. Letter Combinations of a Phone Number (0) | 2024.07.30 |
[BackTrack][Medium] 79. Word Search (0) | 2024.07.26 |
[BackTrack][Medium] 40. Combination Sum II (0) | 2024.07.26 |
[👍][BackTrack][Medium] 90. Subsets II (0) | 2024.07.23 |