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

目次

  1. 背景
  2. Google Tech Dev Guideとは
    1. Google Tech Dev Guideには日本語版がない。
  3. 問題
  4. 問題のねらい
  5. ヒント
    1. ヒント1
    2. ヒント2
    3. ヒント3
    4. ヒント4
    5. ヒント5
    6. ヒント6
  6. 解答
  7. 総当たり(ブルートフォース)
  8. 貪欲法
    1. 計算量の考察
    2. 貪欲法とは
  9. 貪欲法の改善
    1. 計算量の考察
  10. アルファベットの数が少ない時の最適解
  11. アルファベットによらないO(N + L)
  12. まとめ
  13. 関連記事
  14. プログラミング初心者がエンジニアになるには?

背景

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

Google Tech Dev Guideとは

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

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

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

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

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さんがヒントを用意してくれています。
解答に詰まったら見てみましょう。

ヒント1

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

ヒント2

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

ヒント3

貪欲法を使ってみよう

ヒント4

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

ヒント5

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

ヒント6

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

解答

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

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

総当たり(ブルートフォース)

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

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

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

貪欲法

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

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

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

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

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

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

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

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

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

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

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

計算量の考察

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

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

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

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

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

貪欲法とは

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

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

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

貪欲法の改善

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

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

貪欲法はこの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のサブシーケンスかどうかを判定してみます。

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

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

  • ステップ3
    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)です。
ASに使用できるアルファベットの種類で、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"に対して適用してみます。

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

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

  • ステップ3
    次の文字は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内で検索したい文字です。初期状態では各単語の1文字目になります。
配列内には(w=単語,i=最後にSで見つけた文字のカウント)を入れます。
初期状態ではどの文字も見つかっていないので、i = 0となっています。

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

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

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

    1
    2
    3
    4
    5
    a -> []
    b -> [("bale", 0), ("able", 1)]
    l -> [("ale", 1)]
    p -> [("apple", 1)]
    k -> [("kangaroo", 0)]
  • ステップ2
    Sの二文字目はbなので、b[]を処理します。

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2)]
    p -> [("apple", 1)]
    k -> [("kangaroo", 0)]
  • ステップ2
    Sの二文字目はpなので、p[]を処理します。

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2)]
    p -> [("apple", 2)]
    k -> [("kangaroo", 0)]
  • ステップ3
    Sの二文字目はpなので(ry

    1
    2
    3
    4
    5
    a -> [("bale", 1)]
    b -> []
    l -> [("ale", 1), ("able", 2), ("apple", 3)]
    p -> []
    k -> [("kangaroo", 0)]
  • ステップ4
    Sの次はpなので(ry

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

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

  • ステップ4
    次はl(ry

    1
    2
    3
    4
    5
    6
    a -> [("bale", 1)]
    b -> []
    e -> [("ale", 2), ("able", 3), ("apple", 4)]
    l -> []
    p -> []
    k -> [("kangaroo", 0)]
  • ステップ5
    次は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のサンプルを動かす 〜おうむ返しのその先へ〜

プログラミング初心者がエンジニアになるには?

プログラミングを仕事にしたいけど、経験がないので不安だ、
と思っている方は多いと思います。

もちろん、プログラミングを勉強するのも大事ですが、
良い就職エージェントを見つけることで
未経験から就職するためのプロのサポートを受けることができます。

DYM就職は未経験からの就職を得意としているエージェントです。
まずは登録して、プロの意見を聞いてみてはいかがでしょうか?

以下のリンクから登録すると無料の面談が受けられますので、
本気でエンジニアを目指している人はチャレンジしてみてください。