LeetCode) 1048. Longest String Chain

1048. Longest String Chain

문자열 체인을 찾는 문제. 문자열에서 하나씩 빼서 dp를 대조해 제일 큰값을 저장하는 방식으로 풀었다. 이중 for문이고 순환이 많아서 메모리 사용량이 매우 많이 나왔다. 속도로는 중간쯤이였는데, 가장 빠른 코드는 dfs를 활용한 코드였다.

class Solution {
    public int longestStrChain(String[] words) {

        Arrays.sort(words, (String s1, String s2)->s1.length() - s2.length());
        Map<String,Integer> dp = new HashMap<>();

        int maxPath = 1;
        
        for(String word : words){
            
            int length = word.length();
            int size = 0;

            for(int i=0;i<length;i++){
                StringBuilder sb = new StringBuilder(word);
                sb.deleteCharAt(i);    
                size = Math.max(size,dp.getOrDefault(sb.toString(),0));
            }

            dp.put(word,size+1);
            maxPath = Math.max(maxPath,size+1);
        }

        return maxPath;
    }
}