<p>On an alphabet board, we start at position <code>(0, 0)</code>, corresponding to character&nbsp;<code>board[0][0]</code>.</p>

<p>Here, <code>board = [&quot;abcde&quot;, &quot;fghij&quot;, &quot;klmno&quot;, &quot;pqrst&quot;, &quot;uvwxy&quot;, &quot;z&quot;]</code>, as shown in the diagram below.</p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/07/28/azboard.png" style="width: 250px; height: 317px;" /></p>

<p>We may make the following moves:</p>

<ul>
	<li><code>&#39;U&#39;</code> moves our position up one row, if the position exists on the board;</li>
	<li><code>&#39;D&#39;</code> moves our position down one row, if the position exists on the board;</li>
	<li><code>&#39;L&#39;</code> moves our position left one column, if the position exists on the board;</li>
	<li><code>&#39;R&#39;</code> moves our position right one column, if the position exists on the board;</li>
	<li><code>&#39;!&#39;</code>&nbsp;adds the character <code>board[r][c]</code> at our current position <code>(r, c)</code>&nbsp;to the&nbsp;answer.</li>
</ul>

<p>(Here, the only positions that exist on the board are positions with letters on them.)</p>

<p>Return a sequence of moves that makes our answer equal to <code>target</code>&nbsp;in the minimum number of moves.&nbsp; You may return any path that does so.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> target = "leet"
<strong>Output:</strong> "DDR!UURRR!!DDD!"
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> target = "code"
<strong>Output:</strong> "RR!DDRR!UUL!R!"
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target.length &lt;= 100</code></li>
	<li><code>target</code> consists only of English lowercase letters.</li>
</ul>
class Solution {
public:
    string alphabetBoardPath(string target) {
        // Understand: Return minimum number of moves(any path) to spell target word
        // Match: shortest path/dyamic programming/
        // Sub-Problem: 
        //              Find Shortest Path to Each letter
        //              verify if we have spelled the word
        //              a. if at letter, add ! to answer string  
        //              b. find next letter 
        //              c. save next letter to temp
        //              d. calculate path to letter from current letter
        //              f. coordinates (5,1...4) are VOID
        // 0,0
        // 2,1
        vector<std::string>board = {"abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"};
        
        int t = 0, currX = 0, currY = 0, nextX = 0, nextY=0;
        string ans = "";
        while( t < target.length() ) {
            char letter = target[t];  // 'l'
            
            // Locate coordinates of next letter
            for(int i = 0; i < board.size(); i++ ) {
                for(int j = 0; j < board[i].size(); j++) {
                    if(board[i][j] == letter) {nextX = i; nextY = j; break;}
                }      
            }
            
            // if we are already at letter, skip remaining processing
            if(currX == nextX && currY == nextY) {
                ans = ans + '!';
                t++;
                continue;
            }
            
            // Find path to next letter and add path to string
            int deltaX = currX - nextX, deltaY = currY - nextY;
            
            
            
            if(nextX == 5 && nextY == 0) {
                // if negative we move right, else we move left
                if(deltaY < 0) {
                    for(int m = deltaY; m < 0; m++) 
                        ans =  ans + 'R';

                }
                else{
                    for(int m = deltaY; m > 0; m--) 
                        ans =  ans + 'L';
                }
                 // if negative we move down, else we move up
                if(deltaX < 0) {
                    for(int m = deltaX; m < 0; m++) 
                        ans =  ans + 'D';
                }
                else{
                    for(int m = deltaX; m > 0; m--) 
                        ans =  ans + 'U';
                }
            }
            else {
                // if negative we move down, else we move up
                if(deltaX < 0) {
                    for(int m = deltaX; m < 0; m++) 
                        ans =  ans + 'D';
                }
                else{
                    for(int m = deltaX; m > 0; m--) 
                        ans =  ans + 'U';
                } 
                // if negative we move right, else we move left
                if(deltaY < 0) {
                    for(int m = deltaY; m < 0; m++) 
                        ans =  ans + 'R';

                }
                else{
                    for(int m = deltaY; m > 0; m--) 
                        ans =  ans + 'L';
                }
            
            }
           
            // we are now at letter
            // update current position, and hit enter key (add '!' to answer);
            currX = nextX;
            currY = nextY;
            ans = ans + '!';
            
            t++;
        }  
        // letter = l
        // 
    
         
        return ans;
    }
};
9800