Leetcode word break 分词造句

题目描述

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, givens ="leetcode",dict =["leet", "code"].

Return true because"leetcode"can be segmented as"leet code".

给定一个字符串s词典集合，判断字符串s能不能被划分为一个或者多个字典集合中的单词

该题目的解法有很多种：

1、动态规划

动态规划的核心元素：

最优子结构，边界，状态转换方程式

思路：

动态规划的思想需要存储历史信息，这样对于同样的子问题，可以不用再次计算得出，只需要拿过来直接使用就可以了。在这里使用boolean dp[i]来表示到字符串s的第i个字符时，是否可以用dict中的词进行表示。然后，我们可以假设已经求得dp[0..i-1]的结果，所以dp[i]的结果为：dp[j]&&dict.contains(s.substring(j,i))   ,j等于0..i-1。这就是状态转移方程这里不需要最优子结构，只需要满足条件即可。

Java代码：>-<

import java.util.Set; public class Solution { public boolean wordBreak(String s, Set<String> dict) { int length = s.length(); boolean[] dp = new boolean[length + 1]; dp[0] = true; for (int i = 0; i <= length; i++) for(int j = 0 ; j< i;j++) { if(dp[j]&&dict.contains(s.substring(j,i))){ dp[i] = true; break; } } return dp[length]; } }

 解法二：dfs

这个方法其实跟解法一中很类似，用一个二维数组存储在字典中找到的字串。比如‘leet’在字典中，那么数组mem[0][4] = true;

Java代码：

import java.util.Set; public class Solution { int[][] dp; public boolean wordBreak(String s, Set<String> dict) { int len = s.length(); dp = new int[len][len]; //选出s在dict中单词的所有可能 for (int i = 0; i < len; i++) { for (int j = i; j < len; j++) { String tmp = s.substring(i, j+1); if (dict.contains(tmp)) dp[i][j] = 1; } } return dfs(len - 1); } public boolean dfs(int length) { //dfs（0-1）返回true，表示s从0开始到某一长度的字符串得到了匹配 if(length == -1) return true; boolean flag = false; for (int i = 0; i <= length; i++) { if(dp[i][length] == 1) { //找出对应的长度为length-i的单词后，找出长度为i的单词 flag |= dfs(i - 1); } } return flag; } }

解法三：BFS

 BFS需要一个队列来实现。该解法的思路是首先在dict中查找s的前缀（找出所有的），如果有的话，则将该前缀的长度加入队列中。然后还需要使用一个整型visited数组来记录是否访问过（可以节省大量的时间，不然不能通过）。然后依次出队，对取出长度之后的字符串接着进行匹配，直到出队的长度与s的相等，表示匹配完成，返回true，否则返回false。

Java代码：

import java.util.Queue; import java.util.ArrayDeque; import java.util.Set; import java.util.List; import java.util.ArrayList; import java.util.LinkedList; public class Solution { public boolean wordBreak(String s, Set<String> dict) { if(s == null || s.length() == 0) return false; Queue<Integer> qu = new LinkedList(); List<String> list = new ArrayList<String>(dict); for (int i = 0; i< list.size(); i++) if(s.length() >= list.get(i).length() && s.indexOf(list.get(i)) == 0) qu.add(list.get(i).length()); int[] visited = new int[s.length()+1]; while(!qu.isEmpty()){ int top = qu.remove(); if (top == s.length()) return true; if (visited[top] == 0){ visited[top] = 1; String tmp = s.substring(top); for (int i = 0; i < list.size(); i++) if ((tmp.length() >= list.get(i).length()) && (tmp.indexOf(list.get(i))==0)) qu.add(top+list.get(i).length()); } } return false; } }