<?php

namespace leetcode;

use collections\compare\StringComparator;
use collections\set\Set;
use \collections\set\TreeSet;

class Solution {

    /**
     * @param String $s
     * @param String[] $wordDict
     * @return String[]
     */
    public function wordBreak(string $s, array $wordDict): array
    {
        $wordDictSet = new TreeSet(new StringComparator());
        foreach ($wordDict as $word) {
            $wordDictSet->add($word);
        }
        return self::backtrack($s, $wordDictSet, 0);
    }

    /**
     * @param $s
     * @param Set $wordDict
     * @param $start
     * @return String[]
     * @author mzh@shall-buy.com
     * @ref: https://blog.csdn.net/abcdef314159/article/details/120051526
     */
    private static function backtrack($s, Set $wordDict, $start): array
    {
        $ans = array();
        $n = strlen($s);

        for ($i = $start + 1; $i <= $n; $i++) {
            $sub = substr($s, $start, $i-$start);
            // 如果拆解的子串不存在于字典中，就继续拆
            if (!$wordDict->contains($sub)) {
                continue;
            }
            // 走到下面这个地方，说明拆分的子串$str存在于字典中
            // 如果正好拆完了，我们直接把最后一个子串添加到$ans中返回
            if ($i == $n) {
                array_push($ans, $sub);
            } else {
                // 如果没有拆完，我们对剩下的子串继续拆分
                $remains = self::backtrack($s, $wordDict, $i);
                // 然后用当前的子串str和剩下的子串进行拼接（注意如果剩下的子串不能
                // 完全拆分，remain就会为空，就不会进行拼接）
                foreach ($remains as $remainStr) {
                    array_push($ans, $sub .' '. $remainStr);
                }
            }
        }
        return $ans;
    }
}