C#で解くLeetCode「139. Word Break」

概要

エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。

問題

139. Word Break

文字列sと文字列の辞書wordDictが与えられたとき、辞書の単語を使用してsを1つ以上に分割できる場合にtrueを返す。
辞書にある同じ単語が、セグメンテーションで複数回再利用される可能性があることに注意し てください。

"leetcode", ["leet","code"]であればleetとcodeで分割できますね。

"catsandog", ["cats","dog","sand","and","cat"]の場合は分割できません。
catsで始めた場合はandを続けれますがogしか残らず辞書に登録されていないためです。
catでも始められますが、sandを続けた後は同じくogしか残らないため続けられません。

制約

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• sとwordDict[i]は小文字の英字のみからなる。
• wordDictの文字列は全て一意である。

解説

今回は渡された文字列を指定された辞書にある単語だけで分割できるかどうかという問題です。また、分割するために辞書の単語を何度も使用可能です。
この点を踏まえて分割ができていることを記録していきながら探索を進めていきます。

まず初めに『直前の文字まで分割できた』ということを表すためのbool型の配列dpを用意します。この際にdp[0]をtrueにしておきます。
それは『0文字目の文字まで分割できた』ということで1文字目を探索可能にするためです。

var dp = new bool[s.Length + 1];
dp[0] = true;

次に文字を探索していくためfor文で2重にくくります。
注意点として初めのループには末尾を表す変数とし、2重目には先頭を表す変数としてください。

末尾のtailの位置が定まったら先頭から範囲を狭めていき、headからtailまでの文字が単語として登録されているかを確認します。
登録されているのであればtailの位置まで分割成功として次の確認に移ります。
渡された文すべてを確認出来たら最後の結果を返して終了です。

public bool WordBreak(string s, IList<string> wordDict)
{
    var dp = new bool[s.Length + 1];
    dp[0] = true;

    for (int tail = 1; tail <= s.Length; tail++)
    {
        for (int head = 0; head < tail; head++)
        {
            // headの直前まで分割に成功かつheadからtailまでの文字が単語として辞書に登録されているならば
            if (dp[head] && wordDict.Contains(s[head..tail]))
            {
                // 現在のtailまで分割成功とし、tailを伸ばしていく
                dp[tail] = true;
                break;
            }
        }
    }

    //末尾まで分割を成功としているか
    return dp[s.Length];
}

「直前まで分割に成功しているならばそこから始めればいいのでは？」「成功した後に先頭から単語を確認しているのはなぜ？」といった疑問がわくと思います。
勘のいい方は気付いているかもしれませんが、先頭から狭めている理由はスルーした単語が反応するケースがあるためです。
例えば"iamgoodthankyou", ["i","am","go","good","thank","you"]といったケースでgoに反応した後先頭から確認せずに続きから確認した場合odから始まるので反応しなくなってしまいます。
なのでodまでを末尾に含めた後も先頭から確認することでgoodが反応して正しい確認が行われます。

ソースコード

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict)
    {
        var dp = new bool[s.Length + 1];
        dp[0] = true;

        for (int i = 1; i <= s.Length; i++)
        {
            for (int j = 0; j < i; j++)
            {
                // jの位置まで探索が成功している
                if (dp[j] && wordDict.Contains(s[j..i]))
                {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.Length];
    }
}