Shortest Selection Walk on the Alphabet Board

### Problem Start at a on the board with rows `abcde`, `fghij`, `klmno`, `pqrst`, `uvwxy`, `z`. U,D,L,R move one cell in the indicated direction only when that cell exists. An exclamation mark selects the current letter. Return any shortest valid sequence spelling target. Only the letter cells exist, so row 5 has just column 0. ```cpp class Solution { public: string alphabetBoardPath(string target); }; ``` ### Examples **Example 1:** ```text Input: target = "zb" Output: "DDDDD!UUUUUR!" Explanation: Five down moves reach z; five up and one right reach b. These Manhattan distances cannot be shortened. ``` **Example 2:** ```text Input: target = "aa" Output: "!!" Explanation: Select the initial cell twice with no movement. ``` ### Constraints - The target has 1 to 100 characters. - Every target character is a lowercase English letter. ### Contract considerations The output need not match any one reference path; every move must stay on the given board. ```hint Read the boundary condition Do the displayed rows have equal lengths, and must a repeated target letter be selected again? ``` ### What a Strong Answer Covers The output need not match any one reference path; every move must stay on the given board. ### Follow-up Questions Optional practice extension, separate from the original task: How would obstacles on additional board cells change the shortest-path method?