Computer Science Asked by HCSF on July 25, 2020
I am looking at this post:
Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n.
In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string, s, of movement instruction consisting of the letters l and r, where l is an instruction to move one step left and r is an instruction to move one step right. Jamie followed the instructions in s one by one and in order. For example if s=‘rrlr’, she performs the following sequence of moves:
one step right ->one step right ->one step left -> one step right. Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. Recall that a subsequence of a string is obtained by deleting zero or more characters from string.
It has four parameters
The function must return an integer denoting the total number of distinct subsequence of strings that will lead Jamie from point x to point y as this value can be quite large.
Sample Input
rrlrlr
6
1
2
output = 7
Let’s add few more constraints to simply the questions:
I wonder what the runtime is for the proposed solution there:
int distinctSequences (int n, int a, int b, const std::string& actions) {
std::unordered_map<int, int> readyForR, readyForL;
auto res{0};
if (a > 0) {
readyForL.emplace(a, 1);
}
if (a < n) {
readyForR.emplace(a, 1);
}
std::unordered_map<int, int> nextReadyForR, nextReadyForL;
for (auto c: actions) {
nextReadyForR.clear();
nextReadyForL.clear();
if (c == 'r') {
for (auto [pos, count]: readyForR) {
auto pp1{pos+1};
nextReadyForR.emplace(pp1, count);
readyForL[pp1] += count;
if (pp1 == b) res += count;
}
nextReadyForR.erase(n);
std::swap(readyForR, nextReadyForR);
} else {
for (auto [pos, count]: readyForL) {
auto pm1{pos-1};
nextReadyForL.emplace(pm1, count);
readyForR[pm1] += count;
if (pm1 == b) res += count;
}
nextReadyForL.erase(0);
std::swap(readyForL, nextReadyForL);
}
}
return res;
}
What’s its runtime complexity?
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP