技術

Google Tech Dev Guideのコーディング問題解いてみた（ついでに日本語訳も）

目次

  1. 背景
  2. Google Tech Dev Guideとは
    1. Google Tech Dev Guideには日本語版がない。
  3. 問題
  4. 問題のねらい
  5. ヒント
    1. ヒント１
    2. ヒント２
    3. ヒント３
    4. ヒント４
    5. ヒント５
    6. ヒント６
  6. 解答
  7. 総当たり（ブルートフォース）
  8. 貪欲法
    1. 計算量の考察
    2. 貪欲法とは
  9. 貪欲法の改善
    1. 計算量の考察
  10. アルファベットの数が少ない時の最適解
  11. アルファベットによらないO(N + L)
  12. まとめ
  13. 関連記事
  14. PR

背景

こんにちは。 かりんとうマニア(@karintozuki)です。

Google Tech Dev Guideとは

Googleが提供しているコーディングにまつわるコースです。
こちらのリンクから元のサイトが見れます。（英語です。）
https://techdevguide.withgoogle.com/

ネット上のコーディングにまつわる題材をGoogleさんがチョイスして
ひとまとめにコースにした感じで、youtubeやらStack Overflowなどいろいろなところから教材がピックアップされています。

このブログではその中からコーディングチャレンジを抜粋して
日本語で解説しようと思います。
こちらから関連記事がまとめて見られます。
Google Tech Dev Guideのコーディング問題解いてみた 記事一覧

ちなみにこの１問目は割と難し目なので、２問目から始めるのも良いかもしれません。
Google Tech Dev Guideのコーディング問題解いてみた〜その２（ついでに日本語訳も）

Google Tech Dev Guideには日本語版がない。

本家のGoogle Tech Dev Guideには日本語の翻訳がありません。
なので、このブログではGoogle Tech Dev Guideの中でも
コーディングチャレンジを日本語で解説してみようと思っています。

問題

それでは、本題です。

文字列Sと複数の単語Dがあります。
Dの中で最長のSのサブシーケンスを見つけてください。

サブシーケンスの定義
文字列S="abppple"
D={"able", "ale", "apple", "bale", "kangaroo"}
だったときを考えます。

“able”, “ale”, “apple”はSのサブシーケンスです。
これらの単語に含まれる文字はSに含まれています。
また、それらの文字の出現する順番もSの中での順番と同じです。

“bale”はサブシーケンスになりません。
b,a,l,eはSに含まれる文字ですが、出現する順番が違うためです。
(Sの中でb以降にaは登場しません）

“kangaroo”はサブシーケンスではありません。
k,g,r,oはSに含まれないからです。

問題のねらい

アルゴリズムとデータ構造が勉強できます。
それと、計算量オーダー大事。
普通のケースと最悪のケースを想定することに気をつけましょう。

ヒント

Googleさんがヒントを用意してくれています。
解答に詰まったら見てみましょう。

ヒント１

ひとまず複数単語があることは忘れて、一つの単語がサブシーケンスかどうかを判定することだけ考えてみましょう。

ヒント２

サブシーケンスかどうか判定できたら、それを最適化していきましょう。
Sに事前処理をすることで効率的に処理できませんか？

ヒント３

貪欲法を使ってみよう

ヒント４

W=D内の単語数、N=Sの文字数、L=D内の単語の文字数の合計、としたときに
W * NがLよりかなり大きい場合、どうしますか？
例えば、D,Sを事前に処理するなどはできるでしょうか。

ヒント５

Sの文字数がDのサイズよりかなり大きい場合、どうしますか？

ヒント６

事前処理したデータをどのデータ構造で処理しますか？
異なる構造を選んだ際のトレードオフは何でしょうか？
ツリー構造、ディクショナリーなどに収納できるデータはどれでしょうか。

解答

さて、実装できましたか？
いろいろな解放があるので、一つ一つ解説していきます。
解説では、以下の数値を使います。

  • W = D内の単語数
  • N = Sの文字数
  • L = D内の単語の文字数の合計

総当たり（ブルートフォース）

はじめに紹介されている方法は総当たりでやる方法です。
考えられる全てのサブシーケンスを生成して
D内の単語を一つ一つチェックしていきます。

計算量はO(2^N)になります。
ハッシュテーブルやプレフィックス木を使うことで効率をあげることができます。

まあ、これは力技ですな。

貪欲法

貪欲法を使用してD内の単語wがSのサブシーケンスかどうかを判別します。

まずはw[0](単語の一文字目)をSの一文字目から順に探していきます。
w[0]が見つかったら、S内の次の文字からw[1]を探していきます。
これを繰り返し、

  • Sにこれ以上文字がなければwはサブシーケンスではない
  • w内の全部の文字を見つけられれば、wはサブシーケンスである

とサブシーケンスかどうかが判定できます。

実際のデータを使って説明してみます。
S = "abppplee"、w = "ale"の場合で考えてみます。

  • ステップ１
    w[0] = 'a'はSの１文字目に見つかりました。

  • ステップ２
    次に探す文字はw[1] = 'l'です。
    lをSの２文字目以降から探していきます。
    そうするとw[1] = 'l'はSの６文字目で見つかります。

  • ステップ３
    次にw[3] = 'e'をSの７文字目から探していきます。
    w[3] = 'e'はSの7文字目に見つかります。

w内の文字全てが見つかったので、wはSのサブシーケンスです。

という感じでサブシーケンスの判定ができます。

Dを単語の長い順にソートしておけば、
一番はじめに見つかったサブシーケンスが最長のサブシーケンスということになります。

計算量の考察

貪欲法での計算量を考えてみましょう。

D内の単語の単語数合計をW、
Sの文字数をNとした際に、
一回のサブシーケンス判定の計算量はSをスキャンするためにO(N)です。
それをW回だけ実行するので、全体の計算量はO(N*W)です。

これはDに含まれる単語の長さがNに近い時は最適に近い値になります。
最悪のケースとしてはSが長い文字列でDに短い単語しか含まれない場合です。

例えばw=abcdefがS=abcdefgのサブシーケンスかどうかを調べる際は、貪欲法で良い気がします。
ですが、w=zがS=abcdefg~(中略)~xyzのサブシーケンスかどうか調べる際に貪欲法を用いると26回比較しないといけないため、非効率な気がします。

ここでLをDに含まれる単語の文字数の合計と定義します。
この場合、O(N + L)となるアルゴリズムがあれば一番効率がいいですね。
ただ、貪欲法のままだと、計算量はO(N * L)くらいになりそうです。

貪欲法とは

貪欲法という（少なくとも私は）聞き慣れない言葉が出てきました。
これは一般的に判断をする都度で最適な解を選択するアルゴリズムを指すそうです。

貪欲法を用いる処理は一回一回の選択は最適なものを選ぶけど、
処理全体を通しては最適かどうか分からない、ということになります。

この問題でも、対象の文字がSの中で見つかるかを調べるのには最適だけど、全体を通しての処理速度は最適ではない、ということになるでしょうか。
これ以降の方法では、SやDを事前処理することで、その都度の最適解ではなく、全体の最適化を目指します。

貪欲法の改善

wの中の文字cをS内で探す際には以下を満たすiを見つける必要があります。

  • S[i] = cである
  • このiはj（直前に見つけた文字のインデックス）より大きい

貪欲法はこのiを頭からスキャンするため遅くなっています。

これを解決するためにSに事前処理をしてみましょう。
S = "abppplee"だった場合に、文字->[該当文字のSにおけるインデックス]というマップを作ってみましょう。

1
2
3
4
5
a -> [0]
b -> [1]
p -> [2, 3, 4]
l -> [5]
e -> [6, 7]

これを使ってw = "ale"がSのサブシーケンスかどうかを判定してみます。

  • ステップ１
    w[0] = 'a'をまずマップで探すと
    a -> [0]が存在しているので、aはSに使われている文字です。
    次にインデックスを確認します。
    aはwの最初の文字なので、0で良いでしょう。

  • ステップ２
    w[1] = 'l'について、lはマップに存在しています。
    l -> [5]
    直前に見つかった文字のインデックスは0で
    これより大きいインデックスが存在するか確認します。
    そして、5が見つかりました。

  • ステップ３
    w[2] = 'e'について、eはマップに存在しています。
    e -> [6, 7]
    直前に見つかったインデックスは5で、それ以上のインデックスが存在するか確認します。ここでは6が存在していますね。

こうしてw = "ale"内の全ての文字が見つかったので、サブシーケンスである、と言えます。

計算量の考察

このアプローチを使った場合の計算量を考えます。
直前に見つかった文字のインデックスより大きい数字が
存在するかどうかは二分探索を使うことでO(LogN)になります。
参考)バイナリサーチの計算量がO(log_2 n)となる理由
https://qiita.com/yz2cm/items/50abba2810c9bca0e780

なので、全体の計算量はO(N + L * logN)になります。

アルファベットの数が少ない時の最適解

Sに使われるアルファベットの種類が少ない時には
O(N + L)となる方法を紹介します。

正確にはO(N*A + L)です。
AはSに使用できるアルファベットの種類で、a-zならA = 26です。

この方法はSを事前処理する際に、
アルファベットごとにマップを作るところまでは同じですが、
直近見つかった文字のインデックスをjとしたときに
マップ内の配列[j]が、次にその文字が見つかるインデックスを返すようにします。

また、直前に見つかった文字以降にその文字が存在しない時は-1を返します。

言葉で説明すると分かりづらいので、実例をみてみましょう。
S = "abppplee"を処理すると、以下のようになります。

1
2
3
4
5
a -> [0,-1,-1,-1,-1,-1,-1,-1]
b -> [1, 1,-1,-1,-1,-1,-1,-1]
p -> [2, 2, 3, 4,-1,-1,-1,-1]
l -> [5, 5, 5, 5, 5,-1,-1,-1]
e -> [6, 6, 6, 6, 6, 6, 7,-1]

これをw = "ale"に対して適用してみます。

  • ステップ１
    最初の文字はaなので、a -> [0,-1,-1,-1,-1,-1,-1,-1]をみます。
    最初の文字なので、配列内の最初の値をチェックするとa[0] = 0です。

  • ステップ２
    次の文字はlなので、l -> [5, 5, 5, 5, 5,-1,-1,-1]をみます。
    直近で見つかった文字のインデックスは0なので
    返ってくる値はl[0] = 5です。

  • ステップ３
    次の文字はeなので、e -> [6, 6, 6, 6, 6, 6, 7,-1]をみます。
    直近で見つかった文字のインデックスは5なので
    返ってくる値はe[5] = 6です。
    全ての文字が見つかったので、w="ale"はSのサブシーケンスです。

この方法はO(N*A)を事前処理に使うため、Aの種類が多い場合は使えません。
例えばアルファベットだけでなく、日本語も許容した場合などは大変な計算量になりそうですね。

アルファベットによらないO(N + L)

先ほどの方法はアルファベットの文字数に依存しましたが、
そうではない方法を紹介します。

この方法ではD内の単語をまとめて処理します。

事前処理として、Dを以下のようなデータ構造に収納します。

1
2
3
a -> [("able", 0), ("ale", 0), ("apple", 0)]
b -> [("bale", 0)]
k -> [("kangaroo", 0)]

マップのキーにあたる部分（ここではa,b,k）は次にS内で検索したい文字です。初期状態では各単語の１文字目になります。
配列内には(w=単語,i=最後にSで見つけた文字のカウント)を入れます。
初期状態ではどの文字も見つかっていないので、i = 0となっています。

ここからSをスキャンして、文字が見つかった場合は単語を次の文字のマップへ移動させ、iをインクリメントします。
iと単語の文字数が一致した場合、サブシーケンスとして他の配列に格納しておきます。
最終的にSをスキャンし終わって、サブシーケンス配列内で最長の文字列が答えになります。

実際にデータを変化させながらみてみましょう。

  • ステップ１
    Sの一文字目はaです。a[]に含まれる単語を処理すると、
    以下のようになります。

    1
    2
    3
    4
    5
    a -> []
    b -> [("bale", 0), ("able", 1)]
    l -> [("ale", 1)]
    p -> [("apple", 1)]
    k -> [("kangaroo", 0)]

  • ステップ２
    Sの二文字目はbなので、b[]を処理します。

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2)]
    p -> [("apple", 1)]
    k -> [("kangaroo", 0)]

  • ステップ２
    Sの二文字目はpなので、p[]を処理します。

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2)]
    p -> [("apple", 2)]
    k -> [("kangaroo", 0)]

  • ステップ３
    Sの二文字目はpなので(ry

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2), ("apple", 3)]
    p -> []
    k -> [("kangaroo", 0)]

  • ステップ４
    Sの次はpなので(ry

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2), ("apple", 3)]
    p -> []
    k -> [("kangaroo", 0)]

    今回はp[]が存在しないので、変化ないですね。

  • ステップ４
    次はl(ry

    1
    2
    3
    4
    5
    6
    a -> [("bale", 1)]
    b -> []
    e -> [("ale", 2), ("able", 3), ("apple", 4)]
    l -> []
    p -> []
    k -> [("kangaroo", 0)]

  • ステップ５
    次はe(ry

    1
    2
    3
    4
    5
    6
    7
    8
    9
    a -> [("bale", 1)]
    b -> []
    e -> []
    l -> []
    p -> []
    k -> [("kangaroo", 0)]

    // サブシーケンスと判定した文字列を格納する配列
    subsequences[("ale", 3), ("able", 4), ("apple", 5)]

という具合で、サブシーケンスの単語が全部洗い出されました！
この方法なら計算量はO(N + L)になりますね！

まとめ

いかがでしたか？

これらの問題を考える上でのポイントは
計算量を考えることでより良いアルゴリズムにたどり着けるようですね。
また、最悪のケースを考えることで、それが効率的かどうかを判定できるということのようです。

私は今まで計算量などあまり考えずに実装をしていたのですが、
最後の二つの方法とかはどんな人生をあゆんだら思いつくのでしょうか。。。

Google Tech Dev Guideの他の教材も勉強しながら精進していきたいです。

それじゃ今日はこの辺で。

関連記事

こちらの記事もおすすめです。
Spring BootでLINE Botのサンプルを動かす 〜おうむ返しのその先へ〜

PR

あなたの会社はあなたの技術を評価してくれていますか？
技術力を高めようと頑張っているのに、
技術が評価されないような会社にいたらそれは良い環境なのでしょうか？
エンジニアとして技術を高めたいのなら環境を選ぶことも大事です。

レバテックキャリア
エンジニアとして働いていて実務経験があるなら、
求人数の充実具合からレバテックキャリアがおすすめです。
IT転職ではデファクト・スタンダードですね。
▼レバテック　キャリア 登録はこちら▼


Tech Clips
Tech Clipsは年収500万以上＆自社サービスを持った会社に特化した求人サイトです。
首都圏限定になってはしまいますが、
収入を増やしたい、自社サービスを持った企業への転職をしたい人におすすめです。

▼Tech Clips 登録はこちら▼