# Share my AC DP solution

• ``````public class Solution {
public string Encode(string s) {
return Helper(s,0,s.Length-1,new string[s.Length,s.Length]);
}

private string Helper(string s, int low,int high, string[,] dp){

if(low > high)
return "";

if(low == high){
dp[low,high] = s[low]+"";
return dp[low,high];
}

if(dp[low,high] != null){
return dp[low,high];
}

string subStr = s.Substring(low,high-low+1);
string result = subStr;

for(int i = low;i<high;i++){
string r = Helper(s,low,i,dp)+Helper(s,i+1,high,dp);
if(r.Length < result.Length)
result = r;

//Console.WriteLine(low+","+high+":"+result);
}

dp[low,high] = result;

for(int i = 0;i<subStr.Length;i++){
string repeatStr = subStr.Substring(0,i+1);
if(repeatStr != null && subStr.Replace(repeatStr,"").Length == 0){

string ss = subStr.Length/repeatStr.Length+"["+dp[low,low+i]+"]";

if(ss.Length < result.Length)
result = ss;
}
}

dp[low,high] = result;

return dp[low,high];
}

}
``````

• In your second loop, isnt the complexity of substr.Replace() O(n)? So then doesnt that make it so that solving each subproblem is n^2 in the worst case cause you go through all the prefixes for each substring and check to see if it s a repeating pattern?

• Yes, But I don't have any idea how to solve this problem. prefix is not enough.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.