|
1 | 1 | classSolution { |
2 | | -publicintlongestStrChain(String[]words) { |
3 | | -Map<String,Integer>dp =newHashMap<>(); |
4 | | -Set<String>wordSet =Arrays.stream(words).collect(Collectors.toSet()); |
5 | | -intmaxLength =0; |
6 | | -for (Stringword :words) { |
7 | | -maxLength =Math.max(maxLength,dfs(wordSet,dp,word)); |
| 2 | +publicintlongestStrChain(String[]words) { |
| 3 | +Set<String>wordSet =Arrays.stream(words) |
| 4 | + .collect(Collectors.toSet()); |
| 5 | +Map<String,Integer>memo =newHashMap<>(); |
| 6 | +intresult =0; |
| 7 | +for (Stringword :words) { |
| 8 | +result =Math.max(result,dfs(wordSet,memo,word)); |
| 9 | + } |
| 10 | +returnresult; |
8 | 11 | } |
9 | | -returnmaxLength; |
10 | | - } |
11 | | - |
12 | | -privateintdfs(Set<String>wordSet,Map<String,Integer>dp,StringcurrWord) { |
13 | | -if (dp.containsKey(currWord)) { |
14 | | -returndp.get(currWord); |
| 12 | + |
| 13 | +privateintdfs(Set<String>wordSet,Map<String,Integer>memo,Stringword) { |
| 14 | +if (memo.containsKey(word)) { |
| 15 | +returnmemo.get(word); |
| 16 | + } |
| 17 | +intmaxLength =1; |
| 18 | +StringBuildersb =newStringBuilder(word); |
| 19 | +for (inti =0;i <word.length();i++) { |
| 20 | +sb.deleteCharAt(i); |
| 21 | +StringnewWord =sb.toString(); |
| 22 | +if (wordSet.contains(newWord)) { |
| 23 | +intcurrLength =1 +dfs(wordSet,memo,newWord); |
| 24 | +maxLength =Math.max(maxLength,currLength); |
| 25 | + } |
| 26 | +sb.insert(i,word.charAt(i)); |
| 27 | + } |
| 28 | +memo.put(word,maxLength); |
| 29 | +returnmaxLength; |
15 | 30 | } |
16 | | -intmaxLength =1; |
17 | | -StringBuildersb =newStringBuilder(currWord); |
18 | | -for (inti =0;i <currWord.length();i++) { |
19 | | -sb.deleteCharAt(i); |
20 | | -StringnewWord =sb.toString(); |
21 | | -if (wordSet.contains(newWord)) { |
22 | | -maxLength =Math.max(maxLength,1 +dfs(wordSet,dp,newWord)); |
23 | | - } |
24 | | -sb.insert(i,currWord.charAt(i)); |
25 | | - } |
26 | | -dp.put(currWord,maxLength); |
27 | | -returndp.get(currWord); |
28 | | - } |
29 | 31 | } |