[数据结构与算法]LeetCode 打卡 Day 53 —— 单词拆分

1、题目

2、题解

看到题目就想到了动态规划，dp 内存储如下内容，dp[i] 表示从0到 i 是否能够拆分成单词，dp[j] 能够组成单词，当且仅当存在i，满足 dp[i] 能够拆分为单词同时dp[i+1:j] 属于单词。实现代码如下

func wordBreak(s string, wordDict []string) bool {
    dp:=make([]bool, len(s))
    words:=map[string]bool{}

    for _, v := range wordDict { // 构建单词表，便于查询单词是否在字典中
        words[v]=true
    }

    for i:=0; i<len(s); i++ {
        if words[s[0:i+1]] {
            dp[i]=true
        } else {
            for j:=1; j<=i; j++ {
                if dp[j-1]&&words[s[j:i+1]] { // 0到i的字符可以被拆分为单词
                    dp[i]=true
                    break;
                }
            }
        }
    }
    return dp[len(s)-1] 
}

提交结果如下

??注意：切片的索引有如下规律

leetcode 为例，索引 [i,i] 返回空字符串，索引 [i,j+1] 返回索引 i 到 j-1 之间的字符串。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖