いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 809 expressive words

投稿日:

こんにちは

今回の学びは

状態変数が多いならば、データ構造をつかってより楽にできないか?自問すること。

・文字の登場順と回数を問おているのでhashpmapが最適です

 

問題はexpressive-words  mediumです

この問題はどうやらgoogleの電話面接でも聞かれたことがあるようです

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

アイデアは

伸びた数を数えて、違反していないか確認していく方法。

途中、開始以前から同じ文字の場合のカウントをしていなくてk=iでマイナス方向への

whileループを導入した

しかし28/29目のテストケースで落ち、

このスパゲッティソースを管理したくない、タイムアップとうことで

断念した。これまでに45分という時間を使っていた。ちなみに最初の提出までは20分だった。

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は 

len(words)をMとすると

O(N*M)で十分とみた。しかしマイナス方向へのwhileがあるのだが、これもmaxiumで2NにしかならないのでOK。DPも考えたがDPはO(N*len(word)*M)なのでもっと掛かるのでだめ。

 

実際の実装はこちら

class Solution:
    def expressiveWords(self, S: str, words: List[str]) -> int:
        #print(S, words)
        def is_stretchy(S, word):
            i = j = 0
            if S[i] != word[j]: return False
            if len(S) <= len(word)+1: return False
            i = j = 1
            while not(i == len(S) and j == len(word)):
                if j >= len(word): j = len(word) - 1
                if i >= len(S): i = len(S) - 1
                if S[i] == word[j]:
                    i += 1
                    j += 1
                else:
                    if S[i-1] == S[i]:
                        stretchy_cnt = 1
                        k = i
                        while S[k-2] == S[i] and k >= 0:
                            k -= 1
                            stretchy_cnt += 1
                        while S[i-1] == S[i]:
                            stretchy_cnt += 1
                            i += 1
                        if stretchy_cnt < 3:
                            return False
                    else:
                        return False
            return True

        counter = 0
        for word in words:
            if is_stretchy(S, word):
                counter += 1
        return counter

悪くはないが、

デバックしにくい。すでに実装者が混乱している。

28/29のテストケースで落ち、もはやデバッグする気が失せる入力である。

つくりなおしたほうが速いわ!というレベル勘をもって。

discussionを見ると、やはりもっといい回答がたくさんある。

こちら、単純なhashmapで数え上げるプログラム。気に入った。

 

"""
heeellooo
hello
まずはsの登場文字順にrepeat数をかぞえましょう
(h:1, e:3, l:2, o:3)
(h:1, e:1, l:2, o:1)
配列の長さも当然おなじ
文字が全部同じであること。
上のほうが、長さが3以上あること。
下の文字のほうが、常に小さい
"""

実装後です。timespace analysis (時間とスペースの分析)は O(N*M)

ということで

実装は

class Solution:
    def expressiveWords(self, S: str, words: List[str]) -> int:
        def c_count(S):
            if S is None or len(S) == 0: return []
            cc = []
            moji = S[0]
            moji_idx = 0
            for i in range(len(S)+1):
                if i < len(S) and S[i] == moji:
                    pass
                else:
                    cc.append((moji, i - moji_idx))
                    if i < len(S):
                        moji = S[i]
                        moji_idx = i
            return cc

        def is_stretcy(cc1, cc2):
            # cc1 = c_count(S)
            # cc2 = c_count(T)
            # cc is list of tuple('c': int)
            # print(cc1)
            # print(cc2)

            if len(cc1) != len(cc2): return False
            for i in range(len(cc1)):
                if cc1[i][0] != cc2[i][0]: return False
                if cc1[i][1] != cc2[i][1] and cc1[i][1] < 3: return False
                if cc1[i][1] < cc2[i][1]: return False
            return True

        counter = 0
        cc1 = c_count(S)
        for T in words:
            cc2 = c_count(T)
            if is_stretcy(cc1, cc2):
                counter += 1
        return counter

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

文字の現れる順番は必ず同じだからhashmapでなんとかしましょう。

 

ちょっと詳細。

私は最初、この問題をポインターをつかって解こうとしてハマった。うまいひとならこれでも

すんなり実装できるはず。状態はS, Tのポインター、最初マッチのindex, 文字がずれたときの文字数など、結構管理が大変だった。ならば、他にもっと少ない変数で解けないか?使えるデータ構造はないか?と考えて欲しい。

状態変数が多いならば、データ構造をつかってより楽にできないか?自問すること。

文字の登場順と回数を問おているのでhashpmapが最適です

 

「この問題にタグをつけるなら?」

hashmap

 

まとめ

状態変数が多いならば、データ構造をつかってより楽にできないか?自問すること。

・文字の登場順と回数を問おているのでhashpmapが最適です

以上です

-アルゴリズム
-

Copyright© CTOの日記 , 2020 All Rights Reserved.