INTRODUCTION

In this article, we will see about Alphabet Board Path. It is one of the interesting problem, find Alphabet Board Path.

BACKGROUND

Day 14 of 100 Days of Leetcode Programming Challenge. This is one of the top Leetcode Problem. This problem tests our logical skills.

LANGUAGE

I took C# programming language to solve this problem. Since language is independent of the problem. You can use whatever language you wish to solve. Only problem solving approach(logic) is important.

Let’s jump into interesting problem,

Problem

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"], as shown in the diagram below.

We may make the following moves:

  • 'U' moves our position up one row, if the position exists on the board;
  • 'D' moves our position down one row, if the position exists on the board;
  • 'L' moves our position left one column, if the position exists on the board;
  • 'R' moves our position right one column, if the position exists on the board;
  • '!' adds the character board[r][c] at our current position (r, c) to the answer.

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

Return a sequence of moves that makes our answer equal to target in the minimum number of moves.  You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

  • 1 <= target.length <= 100
  • target consists only of English lowercase letters.

Solution with comments

public class Solution {
    public string AlphabetBoardPath(string target) {
        
        //Starting position where a is located
        //0th row and 0th column
        int prevx = 0, prevy = 0;
        
        StringBuilder sb = new StringBuilder();
        
        foreach(char c in target)
        {
            //It calculates the current element row position
            int curx = (c - 'a')/5;
            
            //It calculates the current element column position
            int cury = (c - 'a')%5;
            
            if(curx == prevx && cury == prevy)
            {
                sb.Append('!');        
            }
            else
            {
                FindAndStorePath(sb,prevx,prevy,curx,cury);
                sb.Append('!');
                prevx = curx;
                prevy = cury;
            }
        }
        return sb.ToString();
    }
    
    public void FindAndStorePath(StringBuilder sb,int prevx,int prevy,
                                int curx,int cury)
    {
        //Here the Order is very important
        
        //When the curent element is above to the previous element
        while(prevx > curx)
        {
            sb.Append('U');
            prevx--;
        }
        
        //When the current element is right to the previous element
        while(prevy < cury)
        {
            sb.Append('R');
            prevy++;
        }
        
        //When the current element is left to the previous element
        while(prevy > cury)
        {
            sb.Append('L');
            prevy--;
        }
        
        //When the curent element is below to the previous element
        while(prevx < curx)
        {
            sb.Append('D');
            prevx++;
        }
        
    }
}

Time Complexity : O(n)

Space Complexity : O(1)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s