DoubleWordLadder
SRM 836 · 2022-08-29 · by misof
Problem Statement
All strings in this problem are strings of lowercase English letters ('a'-'z').
You are given two equally long strings A and B. Your primary task is to transform A into B in as few steps as possible.
In each step you must change exactly one letter. You may not change the same letter twice in a row, and you may not change the letter at index i directly from A[i] to B[i].
More formally, the transformation of A to B must look as follows:
- In each step you must select exactly one index into the current word and replace the letter at that index with a different letter. (The new letter must also be a lowercase English letter. We emphasize that the new letter must be different from the current one.)
- You may never select the same index twice in a row. (In other words, in the first step you may select any index you like, but then in each following step you may not select the same index as in the previous step.)
- If you selected the index i and the letter at that index is the original letter A[i], you are not allowed to change it directly into the correct letter B[i].
To illustrate rule 3, suppose A = "yoyo" and B = "lord". In the first step you may change "yoyo" to many different words, including "royo", "yolo", "ooyo", and "yyyo". The three changes forbidden by rule 3 are changing "yoyo" to "loyo", "yoro", and "yoyd".
If you change "yoyo" to "royo", in the second step you can change "royo" to "roxo" but not to "royo" (rule 1), "loyo" (rule 2), or "roro" (rule 3).
Your transformation of A into B can be represented by a
As stated above, your primary goal is to minimize the number of elements in this
Notes
- For the constraints given below a solution always exists.
- Given two different String[]s S and T representing valid solutions with an optimal length, let j be the smallest index such that the strings S[j] and T[j] differ. If S[j] < T[j], we say that S is lexicographically smaller than T.
Constraints
- A will have between 2 and 30 characters, inclusive.
- B will have the same number of characters as A.
- Each character in A and B will be a lowercase English letter ('a'-'z').
"topcoder"
"topcoder"
Returns: {"topcoder" }
If A = B, the optimal sequence of steps has length 0 (do nothing) and thus the optimal return value is a String[] with a single element: the string with which we started and immediately also ended.
"ab"
"cd"
Returns: {"ab", "aa", "ba", "bd", "cd" }
"donation"
"solution"
Returns: {"donation", "aonation", "aoaation", "aoabtion", "aolbtion", "aolution", "solution" }
"solution"
"donation"
Returns: {"solution", "aolution", "aoaution", "aoabtion", "aonbtion", "aonation", "donation" }
"ab"
"ab"
Returns: {"ab" }
Submissions are judged against all 161 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DoubleWordLadder with a public method vector<string> transform(string A, string B) · 161 test cases · 2 s / 256 MB per case