首页 > 代码库 > 【leetcode】Word Break

【leetcode】Word Break

2024-07-12 08:45:53   219人阅读

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".

题解：动态规划

设置数组dp，dp[i,j]表示从s的第i个字母（i=0~s.length-1）开始，长度为j的子字符串是否在字典dict中。则，有以下递推式：

  1. 如果字典包含子字符串s[i,i+j-1],则 dp[i,j] = true；
  2. 如果字典包含子字符串s[i,i+k-1]和字符串s[i+k,i+j]，则dp[i,j] = true;
  3. 否则，dp[i,j] = false;

代码如下：

public class Solution {    public boolean wordBreak(String s, Set<String> dict) {        if(s == null || dict.size() == 0)            return false;        int length = s.length();        boolean[][] dp = new boolean[length][length+1];                for(int len = 1;len <= length;len++){            for(int i = 0;i+len <= length;i++){                String sub = s.substring(i,i+len);                if(dict.contains(sub)){                    dp[i][len] = true;                    continue;                }                                for(int k = 1;k < len;k++){                    if(dp[i][k] && dp[i+k][len-k] )                    {                        dp[i][len] = true;                        break;                    }                }            }        }                return dp[0][length];    }}

对于字符串，substring这个函数返回的是beginIndex和endIndex-1之间的子字符串！


联系
我们