PostAddsense


단어 퍼즐



주어진 단어를 최소로 사용해 목표 문장을 완성하라.

제한 사항

  • strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하다.
  • strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있다.
  • 사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하다.
  • t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하다.
  • 모든 문자열은 알파벳 소문자로만 이루어져 있다.

입출력 예

strstresult
["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]에 넣는다.



참조