|
1 | 1 | packageg3201_3300.s3213_construct_string_with_minimum_cost; |
2 | 2 |
|
3 | 3 | // #Hard #Array #String #Dynamic_Programming #Suffix_Array |
4 | | -// #2024_07_09_Time_182_ms_(100.00%)_Space_61.4_MB_(72.97%) |
| 4 | +// #2024_07_13_Time_1907_ms_(5.01%)_Space_100.9_MB_(5.09%) |
5 | 5 |
|
| 6 | +importjava.util.ArrayList; |
6 | 7 | importjava.util.Arrays; |
| 8 | +importjava.util.Collections; |
| 9 | +importjava.util.HashMap; |
| 10 | +importjava.util.List; |
| 11 | +importjava.util.Map; |
7 | 12 |
|
8 | 13 | publicclassSolution { |
9 | | -privatestaticintinvalid =Integer.MAX_VALUE; |
10 | | - |
11 | | -privatestaticclassNode { |
12 | | -intcost = -1; |
13 | | -Node[]chd =newNode[26]; |
| 14 | +List<Integer>buildKmpPrefix(Stringtarget) { |
| 15 | +List<Integer>w =newArrayList<>(Collections.nCopies(target.length(),0)); |
| 16 | +intk =0; |
| 17 | +inti =1; |
| 18 | +while (i <target.length()) { |
| 19 | +if (target.charAt(i) ==target.charAt(k)) { |
| 20 | +k++; |
| 21 | +w.set(i,k); |
| 22 | +i++; |
| 23 | + }else { |
| 24 | +if (k !=0) { |
| 25 | +k =w.get(k -1); |
| 26 | + }else { |
| 27 | +i++; |
| 28 | + } |
| 29 | + } |
| 30 | + } |
| 31 | +returnw; |
14 | 32 | } |
15 | 33 |
|
16 | | -privateNodert; |
| 34 | +List<List<Integer>>find(List<Integer>prefix,Stringtarget,Stringw) { |
| 35 | +List<List<Integer>>result =newArrayList<>(); |
| 36 | +intm =target.length(); |
| 37 | +intn =w.length(); |
| 38 | +inti =0; |
| 39 | +intk =0; |
| 40 | +while (i <m) { |
| 41 | +if (target.charAt(i) ==w.charAt(k)) { |
| 42 | +i++; |
| 43 | +k++; |
| 44 | + } |
| 45 | +if (k ==n) { |
| 46 | +result.add(Arrays.asList(i -k,i)); |
| 47 | +k =prefix.get(k -1); |
| 48 | + }elseif (i <m &&target.charAt(i) !=w.charAt(k)) { |
| 49 | +if (k !=0) { |
| 50 | +k =prefix.get(k -1); |
| 51 | + }else { |
| 52 | +i++; |
| 53 | + } |
| 54 | + } |
| 55 | + } |
| 56 | +returnresult; |
| 57 | + } |
17 | 58 |
|
18 | 59 | publicintminimumCost(Stringtarget,String[]words,int[]costs) { |
19 | | -rt =newNode(); |
20 | | -intm =words.length; |
21 | | -intn =target.length(); |
22 | | -for (inti =0;i <m; ++i) { |
23 | | -if (words[i].length() <=n) { |
24 | | -insert(words[i],costs[i]); |
| 60 | +List<Integer>targetPrefix =buildKmpPrefix(target); |
| 61 | +Noderoot =newNode(); |
| 62 | +for (intj =0;j <words.length;j++) { |
| 63 | +Stringx =words[j]; |
| 64 | +if (x.length() <320) { |
| 65 | +Nodep =root; |
| 66 | +for (inti =0;i <x.length();i++) { |
| 67 | +charc =x.charAt(i); |
| 68 | +p.children.putIfAbsent(c,newNode()); |
| 69 | +p =p.children.get(c); |
| 70 | +if (i ==x.length() -1) { |
| 71 | +if (p.cost ==null) { |
| 72 | +p.cost =costs[j]; |
| 73 | + }else { |
| 74 | +p.cost =Math.min(costs[j],p.cost); |
| 75 | + } |
| 76 | + } |
| 77 | + } |
25 | 78 | } |
26 | 79 | } |
27 | | -int[]dp =newint[n +1]; |
28 | | -Arrays.fill(dp,invalid); |
| 80 | +Map<Integer,Map<Integer,Integer>>dm = |
| 81 | +getIntegerMapMap(target,words,costs,targetPrefix); |
| 82 | +List<NodeCostPair>d =newArrayList<>(); |
| 83 | +d.add(newNodeCostPair(root,0)); |
| 84 | +int[]dp =newint[target.length() +1]; |
| 85 | +Arrays.fill(dp, -1); |
29 | 86 | dp[0] =0; |
30 | | -for (inti =0;i <n; ++i) { |
31 | | -if (dp[i] ==invalid) { |
32 | | -continue; |
33 | | - } |
34 | | -intnowC =dp[i]; |
35 | | -Nodenow =rt; |
36 | | -for (intj =i;now !=null &&j <n; ++j) { |
37 | | -intch =target.charAt(j) -'a'; |
38 | | -now =now.chd[ch]; |
39 | | -if (now !=null &&now.cost != -1) { |
40 | | -dp[j +1] =Math.min(dp[j +1],nowC +now.cost); |
| 87 | +for (inti =0;i <target.length();i++) { |
| 88 | +charx =target.charAt(i); |
| 89 | +List<NodeCostPair>q =newArrayList<>(); |
| 90 | +Integert =null; |
| 91 | +for (NodeCostPairpair :d) { |
| 92 | +Nodep =pair.node; |
| 93 | +intcost =pair.cost; |
| 94 | +if (p.children.containsKey(x)) { |
| 95 | +Nodew =p.children.get(x); |
| 96 | +if (w.cost !=null) { |
| 97 | +t =t ==null ?cost +w.cost :Math.min(t,cost +w.cost); |
| 98 | + } |
| 99 | +q.add(newNodeCostPair(w,cost)); |
41 | 100 | } |
42 | 101 | } |
| 102 | +t =getInteger(dm,i,dp,t); |
| 103 | +if (t !=null) { |
| 104 | +dp[i +1] =t; |
| 105 | +q.add(newNodeCostPair(root,t)); |
| 106 | + } |
| 107 | +d =q; |
43 | 108 | } |
| 109 | +returndp[target.length()]; |
| 110 | + } |
44 | 111 |
|
45 | | -returndp[n] ==invalid ? -1 :dp[n]; |
| 112 | +privateIntegergetInteger(Map<Integer,Map<Integer,Integer>>dm,inti,int[]dp,Integert) { |
| 113 | +Map<Integer,Integer>qm =dm.getOrDefault(i +1,Collections.emptyMap()); |
| 114 | +for (Map.Entry<Integer,Integer>entry :qm.entrySet()) { |
| 115 | +intb =entry.getKey(); |
| 116 | +if (dp[b] >=0) { |
| 117 | +t =t ==null ?dp[b] +entry.getValue() :Math.min(t,dp[b] +entry.getValue()); |
| 118 | + } |
| 119 | + } |
| 120 | +returnt; |
46 | 121 | } |
47 | 122 |
|
48 | | -privatevoidinsert(Stringwd,intcst) { |
49 | | -intlen =wd.length(); |
50 | | -Nodenow =rt; |
51 | | -for (inti =0;i <len; ++i) { |
52 | | -intch =wd.charAt(i) -'a'; |
53 | | -if (now.chd[ch] ==null) { |
54 | | -now.chd[ch] =newNode(); |
| 123 | +privateMap<Integer,Map<Integer,Integer>>getIntegerMapMap( |
| 124 | +Stringtarget,String[]words,int[]costs,List<Integer>targetPrefix) { |
| 125 | +Map<Integer,Map<Integer,Integer>>dm =newHashMap<>(); |
| 126 | +for (inti =0;i <words.length;i++) { |
| 127 | +Stringword =words[i]; |
| 128 | +if (word.length() >=320) { |
| 129 | +List<List<Integer>>q =find(targetPrefix,target,word); |
| 130 | +for (List<Integer>pair :q) { |
| 131 | +intb =pair.get(0); |
| 132 | +inte =pair.get(1); |
| 133 | +dm.putIfAbsent(e,newHashMap<>()); |
| 134 | +Map<Integer,Integer>qm =dm.get(e); |
| 135 | +if (qm.containsKey(b)) { |
| 136 | +qm.put(b,Math.min(qm.get(b),costs[i])); |
| 137 | + }else { |
| 138 | +qm.put(b,costs[i]); |
| 139 | + } |
| 140 | + } |
55 | 141 | } |
56 | | -now =now.chd[ch]; |
57 | 142 | } |
58 | | -if (now.cost == -1 ||now.cost >cst) { |
59 | | -now.cost =cst; |
| 143 | +returndm; |
| 144 | + } |
| 145 | + |
| 146 | +privatestaticclassNode { |
| 147 | +Map<Character,Node>children; |
| 148 | +Integercost; |
| 149 | + |
| 150 | +publicNode() { |
| 151 | +this.children =newHashMap<>(); |
| 152 | +this.cost =null; |
| 153 | + } |
| 154 | + } |
| 155 | + |
| 156 | +privatestaticclassNodeCostPair { |
| 157 | +Nodenode; |
| 158 | +intcost; |
| 159 | + |
| 160 | +publicNodeCostPair(Nodenode,intcost) { |
| 161 | +this.node =node; |
| 162 | +this.cost =cost; |
60 | 163 | } |
61 | 164 | } |
62 | 165 | } |