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?
3 Asked on February 21, 2021 by always-newbie
1 Asked on February 20, 2021 by saku
1 Asked on February 20, 2021 by rossko_dca
1 Asked on February 17, 2021 by donvitomarco
0 Asked on February 16, 2021 by von-spotz
0 Asked on February 13, 2021 by adam-cole
a star search algorithms euclidean distance graphs shortest path
1 Asked on February 13, 2021 by aviv-barel
5 Asked on February 10, 2021 by gizmo
0 Asked on February 10, 2021 by arthur-b
1 Asked on February 8, 2021 by keith-paton
1 Asked on February 7, 2021 by user3661613
1 Asked on February 6, 2021 by builderthebob00
0 Asked on February 5, 2021 by pookie
1 Asked on February 4, 2021 by retsek680
1 Asked on February 3, 2021 by stark2022
0 Asked on February 1, 2021 by david-grnberger
0 Asked on January 30, 2021 by tzlil
0 Asked on January 29, 2021 by angelic-demonic
Get help from others!
Recent Answers
© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP