139. 单词拆分(leetcode)

LXL's Blog / 2024-09-04 / 原文

https://leetcode.cn/problems/word-break/description/

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 思路较为巧妙,和传统背包定义不同
        // f[i]表示长度为i的字符串能否被wordDict里的单词凑成
        // 状态转义方程也和传统背包不同,需要从题意出发来进行推导
        // 若有j<=i,且 s[j~i]这个子串是 存在于wordDict中的,且f[j]=true
        // 意味着可以由f[j]推导出f[i],即f[i]= f[j] && check(s[j~i])
        // 那么答案就是f[s.length()]
        // 由于求的不是组合而是排列,因此需要先背包再物品
        // 初值:为了方便进行推导,定义f[0]表示空串,为true,f[1]才表示凑成第一个字符的选法,这里f[0]不会影响答案,只是便于计算推导
        // 相当于把s当做背包,s的子串当做物品,判断wrodDict中是否存在,存在即可以凑出来s
        Map<String,Boolean> map = new HashMap<>();
        for(String str:wordDict)map.put(str,true);
        int N = 310;
        boolean[] f=new boolean[N];
        f[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++) // 子串
            {
                String substr=s.substring(j,i);
                Boolean flag=map.get(substr);
                if(f[j]==true && flag!=null && flag==true)
                    f[i]=true;
            }
        }
        return f[s.length()];
        
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 另一种f定义
        // 这类集合中选元素,且是排列问题的,统一可以当做爬楼梯模型来做
        // 如,f[i]表示能否爬到第i阶楼梯,或者说能否构字符串s
        // 以最后一步从哪爬取的来划分子集,且能爬上来的一定是wordDict的谋个元素
        // 即求f[i]的话,是从小于i的楼层爬上来的
        // 能够一步爬上来意味着j~i之间这个子串存在于wordDict中
        // f[i]=f[j] && j~i这个子串存在于wordDict中
        // f[0]表示第0层楼,一定能爬上,为true
        
        Map<String,Boolean> map = new HashMap<>();
        for(String str:wordDict)map.put(str,true);
        int N = 310;
        boolean[] f=new boolean[N];
        f[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++) // 子串
            {
                String substr=s.substring(j,i);
                Boolean flag=map.get(substr);
                if(f[j]==true && flag!=null && flag==true)
                    f[i]=true;
            }
        }
        return f[s.length()];
        
    }
}