NextAndPrev
SRM 572 · 2012-12-13 · by lyrically
SRM 572 · 2012-12-13 · by lyrically · Greedy, Simple Search, Iteration
Problem Statement
Problem Statement
Consider a string consisting of lowercase characters and following two operations that can change it:
int s nextCost and prevCost.
These represent the cost of using each Next and Prev operation, respectively.
You are also given two String s start and goal.
Return the minimum cost required in order to transform start into goal using the above operations.
If transforming start into goal is impossible, return -1 instead.
- Next: Choose a lowercase character and replace its every occurrence with the next character. The next character of 'z' is 'a' ('a' -> 'b', 'b' -> 'c', ..., 'y' -> 'z', 'z' -> 'a').
- Prev: Choose a lowercase character and replace its every occurrence with the previous character. The previous character of 'a' is 'z' ('a' -> 'z', 'b' -> 'a', ..., 'y' -> 'x', 'z' -> 'y').
Constraints
- nextCost and prevCost will each be between 1 and 1000, inclusive.
- start and goal will each contain between 1 and 50 characters, inclusive.
- start and goal will contain the same number of characters.
- Each character in start and goal will be a lowercase character.
Examples
0)
5 8 "aeaae" "bcbbc" Returns: 21
There are several optimal sequences of operations. Here is one of them: "aeaae" -(Next)-> "bebbe" -(Prev)-> "bdbbd" -(Prev)-> "bcbbc". The total cost is 5 + 8 + 8 = 21.
1)
5 8 "aeaae" "bccbc" Returns: -1
It is impossible to transform "aeaae" into "bccbc".
2)
1 1 "srm" "srm" Returns: 0
start and goal may be the same. The cost of an empty sequence of operations is 0.
3)
1000 39 "a" "b" Returns: 975
4)
123 456 "pqrs" "abab" Returns: -1
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NextAndPrev with a public method int getMinimum(int nextCost, int prevCost, string start, string goal) · 103 test cases · 2 s / 256 MB per case