[PHP知识库]单词拆分【php版】

	/**
	 * 采用动态规划 
	 * 记dp[i]表示s的前i个字符组成的字串是否满足题意，
	 * 则 dp[i] = dp[j] & （s[j~i]在字典列表中）    0<=j<i
	 * @param String $s
	 * @param String[] $wordDict
	 * @return Boolean
	 */
	function wordBreak($s, $wordDict) {
		$dictArr = array_flip($wordDict);
		$dp = array_fill(0, strlen($s)+1, false);
		$dp[0] = true;

		for ($i=1,$len=strlen($s); $i<=$len; $i++) {
			for ($j=0; $j<$i; $j++) {
				if ($dp[$j] && array_key_exists(substr($s, $j, $i-$j), $dictArr)) {
					$dp[$i] = true;
				}
			}
		}
		return $dp[strlen($s)];
	}