문자열 목록이 있다고 가정하고 이러한 문자열을 루프로 함께 연결할 수 있습니다. 여기서 각 문자열에 대해 반전 여부를 선택할 수 있습니다. 가능한 모든 루프 중에서 루프를 절단한 후 사전순으로 가장 큰 문자열을 찾아야 합니다. 그러면 루프된 문자열이 일반 문자열이 됩니다. 특히 사전순으로 가장 큰 문자열을 찾으려면 다음 두 단계를 거쳐야 합니다.
모든 문자열을 하나의 루프로 연결합니다. 여기서 일부 문자열을 뒤집을 수도 있고 그렇지 않을 수도 있고 주어진 순서대로 연결할 수 있습니다.
루프의 임의의 위치에 하나의 절단 지점을 잘라서 만드십시오. 그러면 절단 지점의 문자에서 시작하여 루프된 문자열이 일반 문자열로 만들어집니다. 그리고 할 일은 가능한 모든 일반 문자열 중에서 사전순으로 가장 큰 문자열을 찾는 것입니다.
따라서 입력이 "abc", "xyz"와 같으면 "-abcxyz-", "-abczyx-", "-cbaxyz-", "와 같은 루프 문자열을 얻을 수 있으므로 출력은 "zyxcba"가 됩니다. -cbazyx-”, 여기서 '-'는 반복된 상태를 나타내는 데 사용됩니다. 응답 문자열은 네 번째 반복된 문자열에서 가져왔으며 여기서 중간 문자 'a'를 잘라내어 "zyxcba"를 얻을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve() 함수를 정의하면 idx, array strs, rev,
가 필요합니다. -
임시 :=strs[idx]
-
rev가 0이 아니면 -
-
어레이 온도 반전
-
-
str1 :=빈 문자열
-
str2 :=빈 문자열
-
initialize i :=0의 경우 i
수행 -
str1 :=str1 + strs[i]
-
-
for initialize i :=idx + 1, i
-
str2 :=str2 + strs[i]
-
-
초기화 k :=0의 경우 k <임시 크기일 때 업데이트(k를 1만큼 증가), -
-
newOne :=인덱스 k에서 끝까지 temp의 부분 문자열 연결 str2 연결 str1 연결 인덱스에서 temp의 부분 문자열 연결(0에서 k-1까지)
-
ret가 비어 있거나 ret
-
ret :=newOne
-
-
-
findMax() 함수를 정의하면 배열 strs가 필요합니다.
-
for initialize i :=0, i
-
임시 :=strs[i]
-
어레이 온도 반전
-
strs[i] :=(strs[i]> temp이면 strs[i], 그렇지 않으면 temp)
-
-
주요 방법에서 다음을 수행하십시오 -
-
ret :=빈 문자열
-
findMax(문자열)
-
for initialize i :=0, i
-
해결(i, strs, false)
-
해결(i, str, true)
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string ret;
void solve(int idx, vector <string > strs, bool rev){
string temp = strs[idx];
if (rev)
reverse(temp.begin(), temp.end());
string str1 = "";
string str2 = "";
for (int i = 0; i < idx; i++)
str1 += strs[i];
for (int i = idx + 1; i < strs.size(); i++)
str2 += strs[i];
for (int k = 0; k < temp.size(); k++) {
string newOne = temp.substr(k) + str2 + str1 + temp.substr(0, k);
if (ret == "" || ret < newOne) {
ret = newOne;
}
}
}
void findMax(vector<string>& strs){
for (int i = 0; i < strs.size(); i++) {
string temp = strs[i];
reverse(temp.begin(), temp.end());
strs[i] = strs[i] > temp ? strs[i] : temp;
}
}
string splitLoopedString(vector& strs) {
ret = "";
findMax(strs);
for (int i = 0; i < strs.size(); i++) {
solve(i, strs, false);
solve(i, strs, true);
}
return ret;
}
};
main(){
Solution ob;
vector<string> v = {"abc", "xyz"};
cout << (ob.splitLoopedString(v));
} 입력
{"abc", "xyz"} 출력
zyxcba