|
1 | 1 | packageg3201_3300.s3213_construct_string_with_minimum_cost; |
2 | 2 |
|
3 | 3 | // #Hard #Array #String #Dynamic_Programming #Suffix_Array |
4 | | -// #2024_07_13_Time_1907_ms_(5.01%)_Space_100.9_MB_(5.09%) |
| 4 | +// #2024_07_15_Time_261_ms_(88.55%)_Space_67.2_MB_(45.91%) |
5 | 5 |
|
6 | | -importjava.util.ArrayList; |
7 | 6 | importjava.util.Arrays; |
8 | | -importjava.util.Collections; |
9 | | -importjava.util.HashMap; |
10 | | -importjava.util.List; |
11 | | -importjava.util.Map; |
12 | 7 |
|
13 | 8 | publicclassSolution { |
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 | | - } |
| 9 | +privatestaticclassACAutomaton { |
| 10 | +privatestaticclassNode { |
| 11 | +privatecharkey; |
| 12 | +privateIntegerval =null; |
| 13 | +privateintlen; |
| 14 | +privatefinalNode[]next =newNode[26]; |
| 15 | +privateNodesuffix =null; |
| 16 | +privateNodeoutput =null; |
| 17 | +privateNodeparent =null; |
30 | 18 | } |
31 | | -returnw; |
32 | | - } |
33 | 19 |
|
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++; |
| 20 | +publicNodebuild(String[]patterns,int[]values) { |
| 21 | +Noderoot =newNode(); |
| 22 | +root.suffix =root; |
| 23 | +root.output =root; |
| 24 | +for (inti =0;i <patterns.length;i++) { |
| 25 | +put(root,patterns[i],values[i]); |
44 | 26 | } |
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); |
| 27 | +for (inti =0;i <root.next.length;i++) { |
| 28 | +if (root.next[i] ==null) { |
| 29 | +root.next[i] =root; |
51 | 30 | }else { |
52 | | -i++; |
| 31 | +root.next[i].suffix =root; |
53 | 32 | } |
54 | 33 | } |
| 34 | +returnroot; |
55 | 35 | } |
56 | | -returnresult; |
57 | | - } |
58 | 36 |
|
59 | | -publicintminimumCost(Stringtarget,String[]words,int[]costs) { |
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 | | - } |
| 37 | +privatevoidput(Noderoot,Strings,intval) { |
| 38 | +Nodenode =root; |
| 39 | +for (charc :s.toCharArray()) { |
| 40 | +if (node.next[c -'a'] ==null) { |
| 41 | +node.next[c -'a'] =newNode(); |
| 42 | +node.next[c -'a'].parent =node; |
| 43 | +node.next[c -'a'].key =c; |
77 | 44 | } |
| 45 | +node =node.next[c -'a']; |
78 | 46 | } |
79 | | - } |
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); |
86 | | -dp[0] =0; |
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)); |
100 | | - } |
| 47 | +if (node.val ==null ||node.val >val) { |
| 48 | +node.val =val; |
| 49 | +node.len =s.length(); |
101 | 50 | } |
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; |
108 | 51 | } |
109 | | -returndp[target.length()]; |
110 | | - } |
111 | 52 |
|
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()); |
| 53 | +publicNodegetOutput(Nodenode) { |
| 54 | +if (node.output ==null) { |
| 55 | +Nodesuffix =getSuffix(node); |
| 56 | +node.output =suffix.val !=null ?suffix :getOutput(suffix); |
118 | 57 | } |
| 58 | +returnnode.output; |
119 | 59 | } |
120 | | -returnt; |
121 | | - } |
122 | 60 |
|
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 | | - } |
| 61 | +privateNodego(Nodenode,charc) { |
| 62 | +if (node.next[c -'a'] ==null) { |
| 63 | +node.next[c -'a'] =go(getSuffix(node),c); |
141 | 64 | } |
| 65 | +returnnode.next[c -'a']; |
142 | 66 | } |
143 | | -returndm; |
144 | | - } |
145 | | - |
146 | | -privatestaticclassNode { |
147 | | -Map<Character,Node>children; |
148 | | -Integercost; |
149 | 67 |
|
150 | | -publicNode() { |
151 | | -this.children =newHashMap<>(); |
152 | | -this.cost =null; |
| 68 | +privateNodegetSuffix(Nodenode) { |
| 69 | +if (node.suffix ==null) { |
| 70 | +node.suffix =go(getSuffix(node.parent),node.key); |
| 71 | +if (node.suffix.val !=null) { |
| 72 | +node.output =node.suffix; |
| 73 | + }else { |
| 74 | +node.output =node.suffix.output; |
| 75 | + } |
| 76 | + } |
| 77 | +returnnode.suffix; |
153 | 78 | } |
154 | 79 | } |
155 | 80 |
|
156 | | -privatestaticclassNodeCostPair { |
157 | | -Nodenode; |
158 | | -intcost; |
159 | | - |
160 | | -publicNodeCostPair(Nodenode,intcost) { |
161 | | -this.node =node; |
162 | | -this.cost =cost; |
| 81 | +publicintminimumCost(Stringtarget,String[]words,int[]costs) { |
| 82 | +ACAutomatonac =newACAutomaton(); |
| 83 | +ACAutomaton.Noderoot =ac.build(words,costs); |
| 84 | +int[]dp =newint[target.length() +1]; |
| 85 | +Arrays.fill(dp,Integer.MAX_VALUE /2); |
| 86 | +dp[0] =0; |
| 87 | +ACAutomaton.Nodenode =root; |
| 88 | +for (inti =1;i <dp.length;i++) { |
| 89 | +node =ac.go(node,target.charAt(i -1)); |
| 90 | +for (ACAutomaton.Nodetemp =node; |
| 91 | +temp !=null &&temp !=root; |
| 92 | +temp =ac.getOutput(temp)) { |
| 93 | +if (temp.val !=null &&dp[i -temp.len] <Integer.MAX_VALUE /2) { |
| 94 | +dp[i] =Math.min(dp[i],dp[i -temp.len] +temp.val); |
| 95 | + } |
| 96 | + } |
163 | 97 | } |
| 98 | +returndp[dp.length -1] >=Integer.MAX_VALUE /2 ? -1 :dp[dp.length -1]; |
164 | 99 | } |
165 | 100 | } |