LeetCode 471. Encode String with Shortest Length

[Ashish-cr-lc]

man u deserve a lot of veiws.. ur problem solving way is very unique and very good.. this the best channel for sloving leetcode problems..

[anant]

Thanks! Nice explanation! We cannot use pattern directly inside '[' and ']'
-- we need to use its encoded version.
There is an interesting reverse problem (LC 394: Decode String. e.g. input = 3[a2[c]], => 2 'c', 3 'acc', output = accaccacc).

[Charles-rnke]

Would a performance like yours on this problem pass the Google interview?

[PrathamMantri]

I understood the concept, what exactly is happening here. Thanks for explaining. One suggestion, you can record video with preparation of examples and what to show at what point, so that, video wont be too long and you can explain the solution with pauses and getting lost. Nice solution though

[shubhammalik]

1. How its a DP problem, just like that? Any proof or analysis which led you to this decision
2. How did you arrive at the DP state, just like that?

Any analysis or reasoning or intuition behind the decisions would be great.

[Charles-rnke]

Why do you prefer i starting from the right side to left side?

[LeoLeo-nxgi]

Hey my friend, I don't really get your solution on this question. .. can you please say me of some source from where I can get the DP idea about this question ... Please

[monkeyWatts]

good explanation sir, helped me a lot

[boyu]

you don't need to traversal twice about k, you can do it in a loop, which maybe cost less time.
according to your solution, I write a cpp version
class Solution {
public:
std::string encode(std::string const & str) {
if (str.empty()) {
return "";
}
int const strSize = str.size();
dp(strSize,
// initialize to ""
for (int idxLeft = strSize - 1; idxLeft > -1; idxLeft--) {
for (int idxRight = idxLeft; idxRight < strSize; idxRight++) {
std::string curLeftRight = str.substr(idxLeft, idxRight - idxLeft + 1);
dp[idxLeft][idxRight] = curLeftRight;
if (dp[idxLeft][idxRight].size() > MINI_LEN) {
for (int idx = idxLeft; idx < idxRight; idx++) {
// must split the idx from idxLeft to idx(include), and from idx + 1 to idxRight
if (dp[idxLeft][idx].size() + dp[idx + 1][idxRight].size() <
dp[idxLeft][idxRight].size()) {
dp[idxLeft][idxRight] = dp[idxLeft][idx] + dp[idx + 1][idxRight];
}
// }
// for (int idx = idxLeft; idx < idxRight; idx++) {
std::string pattern = str.substr(idxLeft, idx - idxLeft + 1);
if (0 == curLeftRight.size() % pattern.size() &&
"" == replaceAll(curLeftRight, pattern, "")) {
std::string patternAns = / pattern.size()) +
"[" + dp[idxLeft][idx] + "]";
if (patternAns.size() < dp[idxLeft][idxRight].size()) {
dp[idxLeft][idxRight] = patternAns;
}
}
}
}
}
}
return dp[0][strSize - 1];
}

private:
std::string replaceAll(std::string const & str,
std::string const & search,
std::string const & rep = "") {
std::string ans(str);
size_t const repSize = rep.size();
size_t pos = 0;
while ((pos = ans.find(search, pos)) != std::string::npos) {
ans.replace(pos, search.size(), rep);
pos += repSize;
}
return ans;
}

private:
static int const MINI_LEN = 4;

};

[bantyK]

You can give examples of your logic that you are explaining. For example, you could have shown the splitting part with some example, just talking about it wont help visualise the concept to someone who dont know how to solve it.