|
| 1 | +/** |
| 2 | + * DP | Recursion | Memoization |
| 3 | + * Time O(n^4) | Space O(n^4) |
| 4 | + * https://leetcode.com/problems/string-compression-ii/ |
| 5 | + *@param {string} s |
| 6 | + *@param {number} k |
| 7 | + *@return {number} |
| 8 | + */ |
| 9 | +functiongetLengthOfOptimalCompression(s,k){ |
| 10 | +constcache=newMap(); |
| 11 | + |
| 12 | +constdfs=(i,pre,freqOfSameChar,leftK)=>{ |
| 13 | + |
| 14 | +consthash=`${i},${pre},${freqOfSameChar},${leftK}`; |
| 15 | +if(cache.has(hash))returncache.get(hash); |
| 16 | + |
| 17 | +if(leftK<0)returnInfinity; |
| 18 | +if(i===s.length)return0; |
| 19 | + |
| 20 | +constdeleteChar=dfs(i+1,pre,freqOfSameChar,leftK-1); |
| 21 | + |
| 22 | +letkeepChar; |
| 23 | + |
| 24 | +if(s[i]===pre){ |
| 25 | + |
| 26 | +constaddOneOrZero=(freqOfSameChar===1||freqOfSameChar===9||freqOfSameChar===99) ?1 :0; |
| 27 | +keepChar=addOneOrZero+dfs(i+1,pre,freqOfSameChar+1,leftK); |
| 28 | +}else{ |
| 29 | + |
| 30 | +keepChar=1+dfs(i+1,s[i],1,leftK); |
| 31 | +} |
| 32 | + |
| 33 | +cache.set(hash,Math.min(deleteChar,keepChar)); |
| 34 | + |
| 35 | +returncache.get(hash); |
| 36 | +} |
| 37 | + |
| 38 | +returndfs(0,-1,0,k); |
| 39 | +} |
| 40 | + |
| 41 | + |
| 42 | +/** |
| 43 | + * Brute force. |
| 44 | + * Time O(2^n) | Space O(n) |
| 45 | + * https://leetcode.com/problems/string-compression-ii |
| 46 | + *@param {string} s |
| 47 | + *@param {number} k |
| 48 | + *@return {number} |
| 49 | + */ |
| 50 | +vargetLengthOfOptimalCompressionBF=function(s,k){ |
| 51 | + |
| 52 | +construnLengthEncoded=(str)=>{ |
| 53 | +constencodedStr=[]; |
| 54 | +letleft=0; |
| 55 | +letright=1; |
| 56 | + |
| 57 | +while(right<str.length+1){ |
| 58 | +while(str[left]===str[right]){ |
| 59 | +right++; |
| 60 | +} |
| 61 | +constlen=right-left; |
| 62 | +if(len>1){ |
| 63 | +encodedStr.push(str[left],len); |
| 64 | +}else{ |
| 65 | +encodedStr.push(str[left]) |
| 66 | +} |
| 67 | + |
| 68 | +left=right; |
| 69 | +right++; |
| 70 | +} |
| 71 | + |
| 72 | +returnencodedStr.join("").length; |
| 73 | +} |
| 74 | + |
| 75 | +letmin=Infinity; |
| 76 | +constdfs=(i,str,deleteLeft)=>{ |
| 77 | +// console.log(str) |
| 78 | +consthash=`${i}-${deleteLeft}`; |
| 79 | + |
| 80 | +if(i===s.length){ |
| 81 | +min=Math.min(min,runLengthEncoded(str)) |
| 82 | +return; |
| 83 | +} |
| 84 | +if(deleteLeft>0){ |
| 85 | +returnMath.min(dfs(i+1,str+s[i],deleteLeft),dfs(i+1,str,deleteLeft-1)); |
| 86 | +} |
| 87 | +returndfs(i+1,str+s[i],deleteLeft); |
| 88 | +} |
| 89 | + |
| 90 | +dfs(0,"",k); |
| 91 | +returnmin; |
| 92 | +}; |