オットセイの経営日誌

データサイエンス系ベンチャーを経営してます。経営のこと、趣味のことつぶやきます。

LeetCode / Excel Sheet Column Title

https://leetcode.com/problems/excel-sheet-column-title/

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
...

エクセルシートの列名をインデックスに読み換える問題です。実務で必要とされることが多そうな処理ですね。

解答・解説

解法1

まず、Discussionにとても素敵な整理表がありましたので共有します。

f:id:mhiro216:20190823233736p:plain

列名とインデックスの対応はこのようになっています。

一の位は、nを26で割った時の余りに対応しています。割り切れた場合はZに対応します。
十の位は、nを26で割った時の商を、26で割った時の余りに対応しています。割り切れた場合はZに対応します。
百の位以上も同様です。

とすると、{1:'A', 2:'B', ... , 25:'Y', 0:'Z'} というような列名とインデックスの対応を格納した辞書を作成した上で、
nを26で割った余りを格納し、次はnを26で割った商を26で割った余りを格納し、、、を繰り返していけば良いように一瞬思えます。

ただ1つ落とし穴があって、この方法だと2桁以上のZZ, ZZZといったZのみから成る列名でうまくいきません。
例えば702は本来ZZですが、702/26の商は27・余りは0、27/26の商は1・余りは1で、AAZとなってしまいます。
nを26で割った時の商を次のループに回すのではなく、n-1を26で割った時の商をを次のループに回せば、うまくいきます。

from string import ascii_uppercase

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        d = {0:'Z'}
        for i,s in enumerate(ascii_uppercase):
            d[i+1] = s
        result = []
        while n > 0:
            result.append(d[n%26])
            n = (n-1) // 26
        result.reverse()
        return ''.join(result)

nを26で割った時の余りの値を列名に対応させるのは、{1:'A', 2:'B', ... , 25:'Y', 0:'Z'} ではなく {0:'A', 1:'B', ... , 24:'Y', 25:'Z'} として、
n-1を26で割った時の余りの値を列名に対応させても良いので、コードをすっきりさせることができます。

from string import ascii_uppercase

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        d = {}
        for i,s in enumerate(ascii_uppercase):
            d[i] = s
        result = []
        while n > 0:
            result.append(d[(n-1)%26])
            n = (n-1) // 26
        result.reverse()
        return ''.join(result)
解法2

解法1ではstringライブラリを使いましたが、ord(s)でアスキーコードを取り出して数列を作り、chr(n)で文字に戻すことでA-Zの文字列から成るリストを作ることができます。

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        capitals = [chr(x) for x in range(ord('A'), ord('Z')+1)]
        result = []
        while n > 0:
            result.append(capitals[(n-1)%26])
            n = (n-1) // 26
        result.reverse()
        return ''.join(result)