Shorter C++ solution using character lookup array


  • 4
    C

    Use a char map to avoid character to integer calculation.

        string convertToTitle(int n) {
            string map = "ZABCDEFGHIJKLMNOPQRSTUVWXY";
            string res;
        
            while (n) {
                res = map[n-- % 26] + res; 
                n /= 26;
            }
        
            return res;
        }
    

    The idea behind this algorithm is coming from:

    Since we have the following numeric representation mapping to characters:

       A       B             Z
    1+26*0, 2+26*0, ..., 26+26*0
      AA      AB            AZ
    1+26*1, 2+26*1, ..., 26+26*1
      BA      BB            BZ
    1+26*2, 2+26*2, ..., 26+26*2
    

    , and we have the char lookup array:

    A B C ... Z
    0 1 2 ... 25
    

    , the index for the lookup array is always less than the numeric representation by 1.
    Thus, we need to decrement the number n by 1 in order to locate the character in lookup map.

    So we can write:

    string convertToTitle(int n) {
        string map = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string res;
    
        while (n) {
            res = map[(n-1) % 26] + res; 
            n = (n-1) / 26;
        }
    
        return res;
    }
    

    , which is equivalent to:

    string convertToTitle(int n) {
        string map = "ZABCDEFGHIJKLMNOPQRSTUVWXY";
        string res;
    
        while (n) {
            res = map[n % 26] + res; 
            n = (n-1) / 26;
        }
    
        return res;
    }

  • 0
    L

    really cool , much better than my code.


  • 0
    D

    Can you please explain why n is decremented by 1 each time you calculate its modulo? This was the important step I was missing in my own solution. I understand the solution does not work properly without doing this, but I cannot seem to mathematically understand why it is important to do it.


  • 0
    C

    I have updated the solution. The n-- and n /= 26 here is just a "shorthand" for n = (n-1) / 26.


  • 0
    D

    Thanks for taking the time to explain.


  • -1
    S
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.