我要招人

去企业版

首页 > 试题广场 >

单词拆分(一)

[编程题]单词拆分(一)

热度指数：1984 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串和一个字符串数组，在字符串的任意位置拆分任意次后得到的字符串集合是否是给定字符串数组的子集。

数据范围：字符串长度满足 $1 \le len \le 500 \$ ，数组长度满足 $1 \le n \le 1000 \$ ，数组中字符串长度满足 $1 \le len \le 20 \$

示例1

输入

"nowcoder",["now","coder"]

输出

true

示例2

输入

"nowcoder",["no","wcod","der"]

输出

false

示例3

输入

"nowcodernow",["now","coder"]

输出

true

算法知识视频讲解

Java

pein531

动态规划求解，dp[i]表示s[0:i]能不能被词表中的单词拼出来，规定空串可以被拼出来，即dp[0]=true。对于某一个字符s[end]结尾的单词，它如果能被词表中的单词拼出来，那么在前面肯定存在一个以s[start]结尾的单词，它也能够被词表中的单词拼出来，且s[start:end]在词表之中。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串一维数组 
     * @return bool布尔型
     */
    public boolean wordDiv (String s, String[] dic) {
        // write code here
        HashSet<String> wordDict = new HashSet<>();
        for(String word: dic){
            wordDict.add(word);
        }
        boolean[] dp = new boolean[s.length() + 1];      // dp[i]表示s[0:i]能不能被词表中的词拼出来
        dp[0] = true;     // base case:规定空串可以被词表中的词表示
        for(int end = 1; end <= s.length(); end++){
            for(int start = 0; start < end; start++){
                if(dp[start] && wordDict.contains(s.substring(start, end))){
                    // s[0:start]可以用词表中的词拼出来，s[start:end]也在词表中，所以s[0:end]也能被词表中的词拼出来
                    dp[end] = true;
                    break;
                }
            }
        }
        return dp[dp.length - 1];
    }
}

发表于 2021-12-22 17:19:58 回复(0)

牛客5993425号

建议下次找个学过语文的来出题

在字符串的任意位置拆分任意次后得到的字符串集合是否是给定字符串数组的子集。

按答案意思明明是数组子集能否组成字符串

要真按题目的说法，数组就必须包括字符串在任意位置划分的子串

发表于 2022-01-14 23:44:06 回复(2)

Python3

liangzhengjie

from sys import flags
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param dic string字符串一维数组 
# @return bool布尔型
#
class Solution:
    def wordDiv(self , s: str, dic: List[str]) -> bool:
        # write code here
        dp = [False for i in range(len(s))]

        s_dic = set()
        for i in dic:
            s_dic.add(i)

        for i in range(len(s)):
            for j in range(i + 1, len(s) + 1):
                if i == 0:
                    if s[:j] in s_dic:
                        dp[j-1] = True

                if dp[i-1] and s[i:j] in s_dic:
                    dp[j-1] = True

        return dp[-1]

编辑于 2024-04-10 00:28:08 回复(0)

空中转体一周半

动态规划：dp[i]代表字符串s.substring(0,i)可以被拆分。状态转移方程：dp[i] = dp[j] == true && s.substring(j,i)能在词典里被搜索到。

import java.util.*;
public class Solution {
    public boolean wordDiv (String s, String[] dic) {
        boolean dp[] = new boolean[s.length() + 1];
        dp[0] = true;
        for(int i = 1; i <= s.length(); ++i) {
            for(int j = 0; j < i; ++j) {
                if(dp[j] && contains(dic, s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
    public boolean contains(String[] dic, String s) {
        for(int i = 0; i < dic.length; ++i) {
            if(s.equals((dic[i])))return true;
        }
        return false;
    }
}

发表于 2023-03-22 16:05:51 回复(0)

Javascript

牛客283693492号

function wordDiv(s, dic) {
    // write code here
    for (let i = 0; i < dic.length; i++) {
      s = s.replace(new RegExp(`${dic[i]}`, 'g'), '-')
    }
    return !Boolean(s.replace(/\W/g, '').length)
}

发表于 2022-08-23 09:48:24 回复(0)

Java

blue&&lan

public boolean wordDiv (String s, String[] dic) {
        return findWord(s,dic);
    }
    
    boolean findWord(String sc, String[] dic){
        if(sc.length()==0)return true;
        for(int i=0;i<dic.length;i++){
            if(dic[i].length()<=sc.length()&&sc.substring(0,dic[i].length()).equals(dic[i]))
                return findWord(sc.substring(dic[i].length()),dic);
        }
        return false;
    }

发表于 2022-05-31 16:53:37 回复(0)

Java

唐喻铭

递归求解法：

用变量index表示已经遍历到的字符串的下标

从index向后截取字符串，当[index,i)这个字符串在set中出现，就将b[i-1]设置为true

那么下标i之前的字符就不用再看了，index新设置为i

重复操作

递归结束后，发现b[s.length()-1]不为真，表示起码最后的字符串是没有在set中出现，结果为假，返回结果

import java.util.*;
public class Solution {
    public boolean[] b;
    //b[i]=true表示[index,i)是可以在集合中找到
    public boolean wordDiv (String s, String[] dic) {
        b = new boolean[s.length()];
        HashSet<String> set = new HashSet<>();
        for(int i = 0;i < dic.length;i ++) {
            set.add(dic[i]);
        }
        func(s,0,set);//第二个参数表遍历到的字符的下标
        return b[s.length()-1];
    }
    public void func(String s,int index,HashSet<String> set) {
        for(int i = index+1;i <= s.length();i ++) {
            String str = s.substring(index,i);
            if(set.contains(str)) {
                b[i-1] = true;
                func(s,i,set);
            }
        }        
    }
}

发表于 2022-05-25 20:58:06 回复(0)