LeetCode Word Break解题报告

水深无声 2022-05-26 04:57 141阅读 0赞

> 题目描述

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.  
For example, given  
s =”leetcode”,  
dict =\[“leet”, “code”\].  
Return true because”leetcode”can be segmented as”leet code”.  
给定词典集合和字符串，判断字符串是否可以被划分为一个或多个字典集合中的单词

> 动态规划：  
> 动态规划是一种算法思路， 它是利用空间存储历史信息使得未来需要历史信息时不需要重新计算，从而达到降低时间复杂度，是一种用空间换取时间的方法。

三个核心元素：  
最优子结构，边界，状态转换方程式

> 思路：

1.既然动态规划需求存储历史信息，那我们首先应该确认我们要存储的历史信息。这里我用boolean loca\[i\]表示到字符串s的第i个字符时，是否可以用dict中的词来表示。  
2.然后，我们假设我们有loca\[0…i-1\]的结果，那么loca\[i\]的值应该是：loca\[i\] = loca\[j\] && s.substring(j, i + 1) in dict，其中j属于\[0…i - 1\]。这也就是我们所说的状态方程。

其中这里不需要最优子结构，只要满足条件即可，并不需要求最优。  
边界值设loca\[0\] = true  
状态转换方程式：loca\[i\] = loca\[j\] &&s.substring(j,i+1) in dict

import java.util.*;
    public class Solution { 
        public boolean wordBreak(String s, Set<String> dict) {
            int len = s.length();
            boolean[] loca = new boolean[len+1];
            loca[0] = true;
            for(int i=1;i <= len;i++){
                for(int j = 0;j < i;j++){
                    //前j-1个元素in dict且第j~i-1个元素构成的单词in dict，则判断loca[i] = true
                    if(loca[j] && dict.contains(s.substring(j,i))){
                        loca[i] = true;
                        break;
                    }
                }
            }
            return loca[len];
        }
    }

[动态规划算法详解][Link 1]

[Link 1]: https://blog.csdn.net/baidu_28312631/article/details/47418773