문제

단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 ba, na, n, a 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”, “n”, “a”의 4개를 사용하여 문장을 완성할 수 있지만, “ba”, “na”, “na”의 3개만을 사용해도 “banana”를 완성할 수 있습니다. 사용 가능한 단어 조각들을 담고 있는 배열 strs와 완성해야 하는 문자열 t가 매개변수로 주어질 때, 주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 주어진 문장을 완성하는 것이 불가능하면 -1을 return 하세요.

제한사항

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

풀이

이 문제는 DP를 사용한 풀이법과 BFS를 이용한 풀이법이 있다.

DP 풀이법

• 주어진 스트링 t의 각 인덱스마다 스트링배열 strs와 같은 substring이 있는지 확인한다.
• 만약 t.substring(현재 인덱스 - str.length(), 현재 인덱스) 가 str과 같다면 dp[현재 인덱스 -1] (현재 substring이 끝나는 부분)에 dp[현재 인덱스 - str.length() - 1] (현재 substring 시작점 바로 전 부분) 에 1을 더한 수를 저장해준다.
• 만약 현재 substring의 시작점 바로 전 부분의 dp가 0이라면 substring의 끝부분에 해당하는 dp 또한 0으로 유지한다.
• 마지막으로 dp의 끝부분이 0이라면 -1, 아니라면 끝부분의 값을 그대로 반환한다

BFS 풀이법

• 주어진 스트링 t에서 스트링 배열 strs의 원소 str을 찾았을때 노드 안에 그 str의 시작부분과 끝부분의 인덱스를 담는다
• 그래프의 root에서부터 끝부분까지 BFS를 통해 가장 빠른 길을 찾는다
• 가장 빠른 길을 지나면서 지나친 노드의 수를 반환한다
• 만약 길이 없다면 -1을 반환한다

DP 코드

class Solution {
    public int solution(String[] strs, String t) {
        int answer = Integer.MAX_VALUE;
        int[] dp = new int[t.length()];
        
        for (int i = 1; i < t.length() + 1; i++) {
            for (int j = 0; j < strs.length; j++) {
                String puzzle = strs[j];
                if (i - puzzle.length() < 0) continue;
                if (puzzle.equals(t.substring(i - puzzle.length(), i))) {
                    if (i - puzzle.length() == 0) {
                        dp[i - 1] = 1;
                        continue;
                    }
                    if (dp[i - puzzle.length() - 1] > 0) {
                        dp[i - 1] = dp[i - 1] == 0 ? dp[i - puzzle.length() - 1] + 1: 
                        Math.min(dp[i - 1], dp[i - puzzle.length() - 1] + 1);
                    }       
                }
            }
        }
        answer = dp[dp.length - 1];
        if (answer == 0) return -1;
        return answer;
    }
}

BFS 코드

class Solution {
    public int solution(String[] strs, String t) {
        int answer = 0;
        Graph graph = new Graph();
        
        for (int i = 0; i < strs.length; i++) {
            String thisStr = strs[i];
            
            int a = 0;
            int count = 0;
            while (a != -1){
                int add = 0;
                if (count > 0) {
                    add = 1;
                }
                int start = t.indexOf(thisStr, a + add);
                int end = start + thisStr.length();
                if (start != -1) {
                    if (graph.containsNode(start)) {
                        Node node = graph.getNode(start);
                        node.addEdge(end);
                    }
                    else {
                        Node node = new Node(start);
                        node.addEdge(end);
                        graph.addNode(node);
                    }
                    
                }
                a = start;
                count ++;
            } 
        }        
            
        return graph.shortestPath(t.length(), t.length());
    }
    
}

class Graph{
    public HashMap<Integer, Node> nodeMap = new HashMap<Integer, Node>();

    
    public Graph() {
        nodeMap = new HashMap<Integer, Node>();
    }
    
    public void addNode(Node node) {
        nodeMap.put(node.source, node);
    }
    
    public boolean containsNode(int source) {
        return nodeMap.containsKey(source);
    }
    
    public Node getNode(int index) {
        return nodeMap.get(index);
    }
    
    public int shortestPath(int end, int strLeng) {
        Queue<int[]> queue = new LinkedList<>();
        boolean visited[] = new boolean[strLeng];
        
        queue.add(new int[]{0, 0});
        visited[0] = true;
                
        while (queue.size() > 0) {
            int[] currentNode = queue.poll();
            if (nodeMap.containsKey(currentNode[0])){
                ArrayList<Integer> destArr = nodeMap.get(currentNode[0]).destArr;
                for (int i = 0; i < destArr.size(); i++) {
                    if (destArr.get(i) == end) {
                        return currentNode[1] + 1;
                    }
                    if (!visited[destArr.get(i)]){
                        visited[destArr.get(i)] = true;
                        queue.add(new int[]{destArr.get(i), currentNode[1] + 1}); 
                    }           
                }
            }
            
        }
        return -1;
    }
      
}
    
class Node {
    public int source;
    public ArrayList<Integer> destArr;
    
    public Node(int source) {
        this.source = source;
        this.destArr = new ArrayList<Integer> ();
    }
    
    public void addEdge(int end) {
        destArr.add(end);
    }
}

속도는 BFS가 조금더 빠르지만 둘다 효율성 테스트는 통과한다.