단어 퍼즐

문제

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

제한 사항

• 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]에 넣는다.

참조

https://deok2kim.tistory.com/124