スキップしてメイン コンテンツに移動

ゼロから始めるLeetCode Day112「500. Keyboard Row」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day111「682. Baseball Game」

次回
その内

Twitterやってます。

問題

500. Keyboard Row
難易度はEasy。

問題としては、単語のリストwordsが与えられます。
下の画像のような英字キーボードの一行に存在するアルファベットだけで入力できる単語のみをリスト形式で返してください、という問題です。

Example:
Input: [“Hello”, “Alaska”, “Dad”, “Peace”]
Output: [“Alaska”, “Dad”]

AlaskaDadは共に真ん中のキーボードの列に所属するアルファベットのみで構成されていますのでリストで返されています。

解法

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        first = ["q","w","e","r","t","y","u","i","o","p"]
        second = ["a","s","d","f","g","h","j","k","l"]
        third = ["z","x","c","v","b","n","m"]
        ans = []
        for word in words:
            first_count = second_count = third_count = 0
            for letter in word:
                if letter.lower() in first:
                    first_count = first_count + 1
                elif letter.lower() in second:
                    second_count = second_count + 1
                else:
                    third_count = third_count + 1
            if len(word) == first_count or len(word) == second_count or len(word) == third_count:
                ans.append(word)
        return ans

今回は愚直に解いてみました。

各キーボード毎のカウントと単語の長さが等しくなればその単語はキーボードの一列のみで構成されている、ということだと考えました。

まず、各キーボードの列をリストに格納し、wordsを単語に分解、そしてさらに小さい構成要素であるアルファベットに分解しました。

そして条件分岐で各アルファベットがどのキーボードに所属しているかを調べます。

具体的には各カウントをfirst_count,second_count,third_countといった風に用意した変数を使って管理しています。

単語を構成するアルファベットを調べ尽くした後、単語の長さとfirst_count,second_count,third_countのいずれかの値が合致すれば追加すべき要素、ということになるのでリストに追加する、といった風にしています。

最終的にリストansを返せば終わり、といったような解き方となりました。

計算量はfor文を二重に回しているのでO(n^2)、ですかね。

これよりスマートな解き方が出来たよ!という方は是非コメントで教えてくださいお願いします。

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


追記

実行速度は以下のようになっていました。

Runtime: 28 ms, faster than 71.95% of Python3 online submissions for Keyboard Row.

Memory Usage: 14.4 MB, less than 5.49% of Python3 online submissions for Keyboard Row.

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

Braveブラウザを使い始めて結構経った 設定 1 .同期ページを開く 2.QRコードの表示 3.iPhoneで読み取る Braveブラウザを使い始めて結構経った Google Domainsで独自ドメインを持っているBloggerをBrave Creatorsに登録した話。 この記事を書いた頃から僕はBraveしか使わなくなっちゃいましたね〜。 広告がないとネットサーフィンが捗りますし、Braveの直接クリエイターに貢献できるような仕組みが特に気に入っています。Blogger,ひいてはGoogle的にどうなんだって話もありそうですけど、ただのユーザなのでそんなのは気にせず便利なものは使います。 それで本題です。 タイトルのように今回同期機能を設定しました。 余計なことをしていたせいで少しハマったので設定ついでに誰かが困ったときに役に立つように設定方法を残しておこうかと思います。 ちなみにこちらの記事はPCの同期にiPhoneを追加するという設定方法についての解説です。iPhone→PCの同期方法などはまた別の話のようです。 設定 1 .同期ページを開く ブラウザのタブの右上にある上矢印のマークをクリックすると以下のような項目が表示されます。 こちらの同期という欄をクリックします。 すると以下のページが表示されます。 自動的に設定ページの中の同期欄が表示されるわけですね。 2.QRコードの表示 同期欄に同期済みのデバイスを管理という欄があるのでそちらをクリックします。 すると以下のようなページが表示されるのでそちらの中の新たなデバイスを追加、スマホ/タブレットという順にクリックしていくとQRコードが表示されます。 これでこのステップは完了です。 3.iPhoneで読み取る このQRコードをiPhoneで読み取っていく訳ですが、このQRコードはプリインストールされているQRコードで読み取っても正しく処理してくれません。 書いてある通り、iPhoneのBraveブラウザで読み取って上げる必要があります。 なのでひとまずiPhoneでBraveブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ

JavaのindexOf関数はナイーブ法で実装されているらしい

indexOf関数とは 実際のソースを見よう ナイーブ法ってなんぞや indexOf関数とは ドキュメント はここ。 indexOf の細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。 実際のソースを見よう どのように実装されているのかが気になったので jdkの中に存在するsrc.zipを解凍して確認してみることに。 public int indexOf ( String str ) { return indexOf ( str , 0 ) ; } public int indexOf ( String str , int fromIndex ) { return indexOf ( value , 0 , value . length , str . value , 0 , str . value . length , fromIndex ) ; } static int indexOf ( char [ ] source , int sourceOffset , int sourceCount , char [ ] target , int targetOffset , int targetCount , int fromIndex ) { if ( fromIndex >= sourceCount ) { return ( targetCount == 0 ? sourceCount : - 1 ) ; } if ( fromIndex < 0 ) { fromIndex = 0 ; } if ( targetCount == 0 ) { return fromIndex ; } char

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

Webスクレイピングとか 試していたらこれが突然出た。 macOS用公式インストーラーのPython 3.6でCERTIFICATE_VERIFY_FAILEDとなる問題 という記事に解決策が書いてあったが、 python.orgで配布されているmacOS用の公式インストーラーでインストールしたPython 3.6を使い、 urllib.request.urlopen() で https:// のWebページを取得しようとすると、以下のエラーが発生します。 で、このタイトルのエラーに当たっていたよう。 私の場合はPython3.8.5を使っていたので $ /Applications/Python\ 3.8/Install\ Certificates.command というコマンドをターミナルで叩くことで事なきをえた。 読んでないのが悪いとはいえこれはハマる人が多いんじゃなかろうか。