하나의 문자열과 문자열 사전(dictionary)이 주어졌을 때, 주어진 문자열에서 일부 문자를 삭제하여 만들 수 있는 사전 내 가장 긴 문자열을 찾아야 합니다. 만약 가능한 결과가 여러 개라면, 그중 길이가 같은 단어들에 대해서는 사전순(lexicographical order)으로 가장 앞서는 단어를 반환합니다. 만족하는 결과가 없다면 빈 문자열을 반환합니다.
예를 들어 입력 문자열이 "abpcplea"이고 사전 d = ["ale", "apple", "monkey", "plea"]라고 한다면, 결과는 "apple"이 됩니다. "apple"은 "abpcplea"에서 a, b, c, l, e 등의 문자를 적절히 제거하여 만들 수 있는 가장 긴 단어이기 때문입니다.
풀이 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- 두 문자열의 부분 수열 관계를 확인하는
isSubsequence()메서드를 정의합니다. 이 메서드는 s1과 s2를 매개변수로 받습니다. - 포인터 j를 0으로 초기화합니다.
- i를 0부터 s1의 길이까지 순회하며 다음을 수행합니다.
- s2[j]와 s1[i]가 같으면 j를 1 증가시킵니다.
- j가 s2의 길이와 같아지면 루프를 종료합니다.
- 루프 종료 후 j가 s2의 길이와 같으면 true를 반환합니다. 이는 s2가 s1의 부분 수열임을 의미합니다.
- 메인 메서드에서는 다음을 수행합니다.
- 정답 변수 ans를 빈 문자열로 초기화합니다.
- 사전 d를 순회하면서 각 단어 x에 대해 다음 조건을 검사합니다.
- x의 길이가 ans보다 길거나, 길이가 같으면서 x가 ans보다 사전순으로 앞선 경우
- 그리고 isSubsequence(s, x)가 true인 경우 ans를 x로 갱신합니다.
- 최종적으로 ans를 반환합니다.
예제 코드
아래 C++ 구현을 통해 더 자세히 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isSubsequence(string s1, string s2){
int j =0;
for(int i = 0; i < s1.size(); i++){
if(s2[j] == s1[i]){
j++;
if(j == s2.size()) break;
}
}
return j == s2.size();
}
string findLongestWord(string s, vector<string>& d) {
string ans = "";
for(int i = 0; i < d.size(); i++){
string x = d[i];
if(x.size() > ans.size() || (x.size() == ans.size() && (x < ans))){
if(isSubsequence(s, x)) ans = x;
}
}
return ans;
}
};
main(){
vector<string> v = {"ale","apple","monkey","plea"};
Solution ob;
cout << (ob.findLongestWord("abpcplea", v));
}입력
"abpcplea" ["ale","apple","monkey","plea"]
출력
apple
복잡도 분석
사전의 단어 수를 n, 각 단어의 평균 길이를 m, 입력 문자열의 길이를 k라고 할 때, 모든 단어에 대해 부분 수열 검사를 수행하므로 시간 복잡도는 O(n × k)입니다. 공간 복잡도는 추가 배열 없이 포인터만 사용하므로 O(1)입니다.