LeetCode / First Unique Character in a String

今日は、いくら計算量を頑張って削減してもPythonの超えられない壁があるよ、ということを身を以て伝えてくれる問題です。

https://leetcode.com/problems/first-unique-character-in-a-string/

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

文字列中で出現する回数が1度のみの文字について、初めて登場するインデックスを返す問題です。

解答・解説

解法1

素朴に書いて解くこともできます。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        d = {}
        for c in s:
            if c not in d:
                d[c] = 1
            else:
                d[c] += 1
        uniques = []
        for k,v in d.items():
            if v == 1:
                uniques.append(k)
        if uniques:
            for i,c in enumerate(s):
                if c in uniques:
                    return i
        else:
            return -1

時間計算量、空間計算量ともにとなりますが、空間計算量についてはdとuniquesの2つ変数を作ってしまっているので少し無駄が多い。

解法2

Pythonであれば、collections.Counterを使うとよりスッキリ書ける。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = collections.Counter(s)    
        for i, c in enumerate(s):
            if count[c] == 1:
                return i
        return -1

解法3

Discussionを見ていて面白かったのが以下の解法。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        letters = 'abcdefghijklmnopqrstuvwxyz'
        indexes = [s.index(l) for l in letters if s.count(l) == 1]
        return min(indexes) if len(indexes) > 0 else -1

解法2などの時間計算量は、countとfindの2回ループを回す必要があるので、いわばになっていますが、この解法はアルファベットの文字数26個分のループも加わっているのでになっている。
しかし、こちらの解法の方が爆速で速いのです。私のsubmitしたときは、解法2が84msかかったのに対し、解法3では44msでした。

その理由ですが、string.indexはCで実装された関数だから、ということのようです。

Its only faster because s.index is a C function that python is calling. So you are changing the python loop to be the 26 characters, and the C loop is doing the heavy lifting searching the string. From an algo perspective this is slower than the others. But good to know for python users for runtime speedup

ここでもC系言語の威力を感じます。今年中にC++の学習に取り組めるだろうか。。。