动态规划之139 Word Break

题目链接：https://leetcode-cn.com/problems/word-break/

参考链接：https://blog.csdn.net/c_flybird/article/details/80703494

　　　　　http://www.cnblogs.com/springfor/p/3874731.html

这种题目一般出现字符串、子数组都需要使用动态规划

dp[i]，前i个字符串是否在字典中。

dp[0]=true;空字符肯定是在字典中。

public boolean wordBreak(String s, List<String> wordDict) {

        boolean dp[]=new boolean[s.length()+1];

        Arrays.fill(dp, false);

        dp[0]=true;

        for (int i = 1; i < dp.length; i++) {

            for (int j = i - 1; j >= 0; j--)

            {

                if (dp[j] && wordDict.contains(s.substring(j, i)))

                {

                    dp[i] = true;

                    break;

                }

            }

        }

        return dp[s.length()];

    }

巴特西

动态规划之139 Word Break

最新文章

热门文章