ゼロから始めるLeetCode Day101「387. First Unique Character in a String

• 概要
• 問題
• 解法

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day100「108. Convert Sorted Array to Binary Search Tree」

次回
ゼロから始めるLeetCode Day102「322. Coin Change」

Twitterやってます。

問題

387. First Unique Character in a String
難易度はEasy。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、文字列が与えられるので、その中から最初の反復されない文字（文字列の中に一度しか表示されない文字）を見つけ、そのインデックスを返す、というものです。なお、存在しない場合は -1 を返します。

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”
return 2.

解法

軽くサクサクっと解けるような考え方としてはCounterを使うと手っ取り早いですね。

collections.Cpunterを使うと文字列の中にどの文字が何回表示されるかを出してくれます。

例えば、今回のテストケースであるleetcodeの場合は以下のようになります。

count = collections.Counter(s)
print(count)
        
# Counter({'e': 3, 'l': 1, 't': 1, 'c': 1, 'o': 1, 'd': 1})

これでどの文字が何回出るかは分かります。
ここまですれば後はenumerateを使って与えられる文字列sからenumerateを使ってインデックスとワードを抜き出し、count[word]が1であればインデックスを返せばよく、最後まで存在しなければ-1を返せば良い、となるわけです。

その流れをコードにしてみると以下の通りです。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        count = collections.Counter(s)
        print(count)
        for index,word in enumerate(s):
            if count[word] == 1:
                return index
        return -1
# Runtime: 96 ms, faster than  83.49%  of  Python3  online submissions for  First Unique Character in a String.
# Memory Usage: 14 MB, less than  34.96%  of  Python3  online submissions for  First Unique Character in a String.

Qiitaでの投稿を終わらせたので、新鮮な気持ちでまだまだ続けられそうです。

毎日更新するかどうかは分かりませんが、とりあえず60問解き終わるまでは続けたいですね。

では今回はここまで。お疲れ様でした。