Leetcode 1531 String Compression II
Vložit
- čas přidán 26. 12. 2023
- Solution to leetcode problem 1531. String Compression II
I have used Dynamic Programming DP to solve this problem.
Telegram Links:
t.me/+FieKB7Ds6j02Y2Y1
t.me/+JU-ZF-oDjX4xYjBl
Problem Link: leetcode.com/problems/string-...
Solution Link: leetcode.com/problems/string-...
Check out our community of 400+ people: t.me/+FieKB7Ds6j02Y2Y1
Thanks
Welcome!!
This is my java solution: Logically It makes sense to me but I am having trouble with the testcases, any pointers will help:
class Solution {
public int getLengthOfOptimalCompression(String s, int k) {
int[][] x = new int[s.length() + 1][k + 1];
for(int[] j : x){
Arrays.fill(j, -1);
}
return find(s, k, 0, x, Character.MIN_VALUE, 0);
}
int find(String s, int k, int index, int[][] x, char cur, int charcount){
if(k == 0 || index >= s.length()){
return Calculate_len(s, index);
}
if(x[index][k] != -1){
return x[index][k];
}
int count = 0;
if(cur != s.charAt(index)){
String num = String.valueOf(charcount);
int val = 0;
if(num.equals("1")){
val = 1;
}
else if(num.equals("0")){
val = 0;
}
else{
val = num.length() + 1;
}
// System.out.println(num + " " + val);
count = Math.min(find(s, k, index + 1, x, s.charAt(index),1) + val, find(s, k - 1, index + 1, x, cur, charcount));
}
else{
count = Math.min(find(s, k, index + 1, x, s.charAt(index),charcount + 1), find(s, k - 1, index + 1, x, cur, charcount));
}
x[index][k] = count;
// System.out.println(x[index][k] + " " + index + " " + k);
return x[index][k];
}
int Calculate_len(String s, int index){
if(index >= s.length()){
return 0;
}
String ns = s.substring(index);
int i = 0;
int fin_count = 0;
while(i < ns.length()){
int count = 1;
while(i < ns.length() - 1 && ns.charAt(i) == ns.charAt(i + 1)){
count++;
i++;
}
if(count == 1){
fin_count++;
}
else{
String num = String.valueOf(count);
fin_count += (num.length() + 1);
}
i++;
}
return fin_count;
}
}
class Solution {
public:
int dp[102][102];
int find(int n){
if(n==1) return 1;
if(n>1 and n=10 and n
in 10:19 why to take a2 for a7 and for a10 to a3 I did'nt understand this
It's the length of the new String i.e a7 has a length of 2 and a10 has a length of 3