주어진 단어를 최소로 사용해 목표 문장을 완성하라.
제한 사항
- strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하다.
- strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있다.
- 사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하다.
- t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하다.
- 모든 문자열은 알파벳 소문자로만 이루어져 있다.
입출력 예
strs | t | result |
["ba","na","n","a"] | "banana" | 3 |
["app","ap","p","l","e","ple","pp"] | "apple" | 2 |
["ba","an","nan","ban","n"] | "banana" | -1 |
코드
#include <algorithm>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
int dp[20001];
int solution(vector<string> strs, string t) {
unordered_set<string> us (strs.begin(),strs.end());
for (int i = 1; i <= t.size(); i++) {
dp[i] = 20001;
for (int j = 1; j <= 5; j++) {
if (i-j<0) break;
if (us.find(t.substr(i-j,j)) != us.end())
dp[i] = min(dp[i], dp[i-j]+1);
}
}
return (dp[t.size()] == 20001) ? -1 : dp[t.size()];
}
풀이
문장 t를 최소 길이 1부터 최대 길이 t.size()만큼 분할해 단어를 만들어 strs의 unordered_set인 us에서 찾는다. 단어가 존재하면 dp[i]와 단어 길이만큼 뺀 값 dp[i-j] + 1 중 최소값을 dp[i]에 넣는다.
참조
최근 덧글