According to https://cplusplus.com/reference/string/string/substr/↵
Complexity = Unspecified, but generally linear in the length of the returned object.↵
↵
However, I believe in practice it's much faster, specially for repeated calls with same start_pos.↵
↵
Example problem:↵
https://leetcode.com/contest/weekly-contest-377/problems/minimum-cost-to-convert-string-ii/↵
↵
Solution from contest winner below↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
const int N = 300;↵
const long long INF = 0x3F3F3F3F3F3F3FLL;↵
↵
long long dis[N][N];↵
↵
class Solution {↵
public:↵
long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {↵
map<string, int> label;↵
for (auto& v : original) {↵
label[v];↵
}↵
for (auto& v : changed) {↵
label[v];↵
}↵
int total = 0;↵
for (auto& it : label) {↵
it.second = total++;↵
}↵
↵
for (int i = 0; i < total; ++i) {↵
for (int j = 0; j < total; ++j) {↵
dis[i][j] = INF;↵
}↵
dis[i][i] = 0;↵
}↵
↵
for (int i = 0; i < original.size(); ++i) {↵
int u = label[original[i]];↵
int v = label[changed[i]];↵
↵
dis[u][v] = min(dis[u][v], (long long) cost[i]);↵
}↵
for (int k = 0; k < total; ++k) {↵
for (int i = 0;i < total; ++i) {↵
for (int j = 0; j < total; ++j) {↵
if (i != j && j != k && k != i) {↵
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);↵
}↵
}↵
}↵
}↵
↵
vector<int> lens;↵
for (auto& v : original) {↵
lens.push_back(v.size());↵
}↵
sort(lens.begin(), lens.end());↵
lens.erase(unique(lens.begin(), lens.end()), lens.end());↵
↵
int n = source.size();↵
vector<long long> dp(n + 1, INF);↵
dp[0] = 0;↵
↵
for (int i = 0; i < n; ++i) {↵
if (source[i] == target[i]) {↵
dp[i + 1] = min(dp[i + 1], dp[i]);↵
}↵
for (int l : lens) {↵
if (i - l + 1 >= 0) {↵
string s = source.substr(i - l + 1, l);↵
string t = target.substr(i - l + 1, l);↵
auto u = label.find(s);↵
auto v = label.find(t);↵
if (u != label.end() && v != label.end()) {↵
dp[i + 1] = min(dp[i + 1], dp[i - l + 1] + dis[u->second][v->second]);↵
}↵
}↵
}↵
}↵
if (dp[n] >= INF) {↵
return -1;↵
}↵
return dp[n];↵
}↵
};↵
~~~~~↵
</spoiler>↵
↵
↵
My analysis of the time complexity for the code above:↵
I think substr() call should result in timeout.↵
STL says complexity of substr(x, len) = len.↵
Therefore, the dp loop is n * lens.size() * max_len↵
where, n = source.size(), and max_len = max(lens[i]) for all i.↵
↵
Eg. in the case where n = 1000, and we have lens = [900, 901, ..., 999].↵
Therefore,↵
↵
1. Outer loop > `for (int i = 0; i < n; ++i)` n = 1000,↵
↵
2. Inner loop > `for (int l : lens)`, lens = [900, 901, ..., 999]↵
↵
3. Inside inner loop. we call substr(st, l), in O(l). But max(l) = n↵
↵
↵
Thus, since max(l) = max_len = 999,↵
↵
- Time Complexity = n * lens.size() * max_len↵
↵
- Time Complexity = n * lens.size() * n↵
↵
- Time Complexity = 1000*100*1000, which should TLE↵
↵
↵
There must be something going on making substr() more efficient.↵
My guess is caching susbtr() calls so substr(i, x+d), uses previously queried substr(i, x),↵
↵
**Would love to understand more about the optimization going on in substr(). Or would this solution always give TLE for this test case, indicating that it could be hacked (even if not supported in Leetcode)?**↵
↵
Only thing I found is from https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring↵
↵
<spoiler summary="stackoverflow">↵
Old answer: pre-Java 7↵
Undocumented — but in practice O(1) if you assume no garbage collection is required, etc.↵
↵
It simply builds a new String object referring to the same underlying char[] but with different offset and count values. So the cost is the time taken to perform validation and construct a single new (reasonably small) object. That's O(1) as far as it's sensible to talk about the complexity of operations which can vary in time based on garbage collection, CPU caches etc. In particular, it doesn't directly depend on the length of the original string or the substring.↵
</spoiler>↵
↵
↵
↵
↵
↵
Complexity = Unspecified, but generally linear in the length of the returned object.↵
↵
However, I believe in practice it's much faster, specially for repeated calls with same start_pos.↵
↵
Example problem:↵
https://leetcode.com/contest/weekly-contest-377/problems/minimum-cost-to-convert-string-ii/↵
↵
Solution from contest winner below↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
const int N = 300;↵
const long long INF = 0x3F3F3F3F3F3F3FLL;↵
↵
long long dis[N][N];↵
↵
class Solution {↵
public:↵
long long minimumCost(string source, string target, vector<string>& original, vector<string>& changed, vector<int>& cost) {↵
map<string, int> label;↵
for (auto& v : original) {↵
label[v];↵
}↵
for (auto& v : changed) {↵
label[v];↵
}↵
int total = 0;↵
for (auto& it : label) {↵
it.second = total++;↵
}↵
↵
for (int i = 0; i < total; ++i) {↵
for (int j = 0; j < total; ++j) {↵
dis[i][j] = INF;↵
}↵
dis[i][i] = 0;↵
}↵
↵
for (int i = 0; i < original.size(); ++i) {↵
int u = label[original[i]];↵
int v = label[changed[i]];↵
↵
dis[u][v] = min(dis[u][v], (long long) cost[i]);↵
}↵
for (int k = 0; k < total; ++k) {↵
for (int i = 0;i < total; ++i) {↵
for (int j = 0; j < total; ++j) {↵
if (i != j && j != k && k != i) {↵
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);↵
}↵
}↵
}↵
}↵
↵
vector<int> lens;↵
for (auto& v : original) {↵
lens.push_back(v.size());↵
}↵
sort(lens.begin(), lens.end());↵
lens.erase(unique(lens.begin(), lens.end()), lens.end());↵
↵
int n = source.size();↵
vector<long long> dp(n + 1, INF);↵
dp[0] = 0;↵
↵
for (int i = 0; i < n; ++i) {↵
if (source[i] == target[i]) {↵
dp[i + 1] = min(dp[i + 1], dp[i]);↵
}↵
for (int l : lens) {↵
if (i - l + 1 >= 0) {↵
string s = source.substr(i - l + 1, l);↵
string t = target.substr(i - l + 1, l);↵
auto u = label.find(s);↵
auto v = label.find(t);↵
if (u != label.end() && v != label.end()) {↵
dp[i + 1] = min(dp[i + 1], dp[i - l + 1] + dis[u->second][v->second]);↵
}↵
}↵
}↵
}↵
if (dp[n] >= INF) {↵
return -1;↵
}↵
return dp[n];↵
}↵
};↵
~~~~~↵
</spoiler>↵
↵
↵
My analysis of the time complexity for the code above:↵
I think substr() call should result in timeout.↵
STL says complexity of substr(x, len) = len.↵
Therefore, the dp loop is n * lens.size() * max_len↵
where, n = source.size(), and max_len = max(lens[i]) for all i.↵
↵
Eg. in the case where n = 1000, and we have lens = [900, 901, ..., 999].↵
Therefore,↵
↵
1. Outer loop > `for (int i = 0; i < n; ++i)` n = 1000,↵
↵
2. Inner loop > `for (int l : lens)`, lens = [900, 901, ..., 999]↵
↵
3. Inside inner loop. we call substr(st, l), in O(l). But max(l) = n↵
↵
↵
Thus, since max(l) = max_len = 999,↵
↵
- Time Complexity = n * lens.size() * max_len↵
↵
- Time Complexity = n * lens.size() * n↵
↵
- Time Complexity = 1000*100*1000, which should TLE↵
↵
↵
There must be something going on making substr() more efficient.↵
My guess is caching susbtr() calls so substr(i, x+d), uses previously queried substr(i, x),↵
↵
**Would love to understand more about the optimization going on in substr(). Or would this solution always give TLE for this test case, indicating that it could be hacked (even if not supported in Leetcode)?**↵
↵
Only thing I found is from https://stackoverflow.com/questions/4679746/time-complexity-of-javas-substring↵
↵
<spoiler summary="stackoverflow">↵
Old answer: pre-Java 7↵
Undocumented — but in practice O(1) if you assume no garbage collection is required, etc.↵
↵
It simply builds a new String object referring to the same underlying char[] but with different offset and count values. So the cost is the time taken to perform validation and construct a single new (reasonably small) object. That's O(1) as far as it's sensible to talk about the complexity of operations which can vary in time based on garbage collection, CPU caches etc. In particular, it doesn't directly depend on the length of the original string or the substring.↵
</spoiler>↵
↵
↵
↵
↵
↵
