You are given a string s and two integers i and j where i < j. Let’s say p is an infinite string of s repeating forever. Return the substring of p from indexes [i, j).
Example 1
Input
s = “tiger”
i = 6
j = 8Output
“ig”Example 2
Input
s = “hi”
i = 2
j = 6Output
“hihi”
Index into Infinite String with 3 Parts
We can divide the [i:j) range into 3 parts: s[a:],s*t, and s[:b] where we need to figure out the values of a, t and b.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | string solve(string s, int i, int j) { int n = s.size(); int t = i / n; i = i % n; j -= t * n; string ans = s.substr(i, j - i); if (j > n) { t = (j - n) / n; j = (j - n) - t * n; while (t --) { ans += s; } ans += s.substr(0, j); } return ans; } |
string solve(string s, int i, int j) {
int n = s.size();
int t = i / n;
i = i % n;
j -= t * n;
string ans = s.substr(i, j - i);
if (j > n) {
t = (j - n) / n;
j = (j - n) - t * n;
while (t --) {
ans += s;
}
ans += s.substr(0, j);
}
return ans;
}However, this method is error-prone and especially with the index calculation which may go wrong.
Compute the Corresponding Index from Infinite
We can compute directly the index which is a lot simpler:
1 2 3 4 5 6 7 8 | string solve(string s, int i, int j) { int n = s.size(); string ans = ""; for (int k = i; k < j; ++ k) { ans += s[k % n]; } return ans; } |
string solve(string s, int i, int j) {
int n = s.size();
string ans = "";
for (int k = i; k < j; ++ k) {
ans += s[k % n];
}
return ans;
}This is a much cleaner method.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
310 wordsloading...
Last Post: From Breadth First Search Algorithm to Dijkstra Shortest Distance from Source to Every Vertex
Next Post: Algorithms to Convert Binary Linked List to Integer
