思路:动态规划

先把这道题搞懂：139. 单词拆分

本题实际就是Leetcode139 + 寻找dp数组中的具体方案：

由于题目要求优先从左到右长度尽量长的单词去切分，比如:

["ab" , "a" , "b" , "c"]

给定"abc" , 要拆成"ab","c" , 而不是"a","b","c"。

所以我们需要倒着进行动态规划:

令$dp[i]$ 代表$s[i:]$ 这一后缀是否能被组成出来。

然后$i$从$n-1$到$0$ 进行dp.每次转移的时候，我们考虑的是尽量长的单词，

也就是假设$i = k$ , 如果有两个情况同时满足:

1.$dp[k-5] = 1$ 且 $s[k:k+5]$ 存在于单词表

2.$dp[k-10] = 1$ 且 $s[k:k+10]$ 存在于单词表

我们肯定是选情况2下的方案。因为这样能满足从左到右长度尽量长的单词去切分

除此之外，第一行可能有逗号，那么就是先split，然后再逐行dp

C++

#include <bits/stdc++.h>

using namespace std;

string joinString (vector<string> arr , string s){
    string res = "";
    for (auto x : arr){
        res += x;
        res += s;
    }
    return res.substr(0 , res.size() - s.size());
}
// 动态规划求解字符串s是否能被某单词列表组成
// 在有多种拆分情况下，考虑从左到右长度尽量长的单词去切分
string solve(const string& s, const vector<string>& words) {
    int n = s.length();
    vector<bool> f(n + 1, false); // f[i]表示s[i:]这个后缀能被某单词列表组成
    f[n] = true; // 空串能被某单词列表组成

    for (int i = n; i >= 0; i--) { // 从后往前求解
        for (const string& x : words) { // 遍历单词列表
            int m = x.length(); // 单词长度
            if (i + m <= n && s.substr(i, m) == x && f[i + m]) { // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
                f[i] = true; // 则s[i:]能被某单词列表组成
                break;
            }
        }
    }

    // 接下来考虑如何从f这个动态规划数组中拆出具体方案
    vector<string> res; // 记录分解方式
    if (!f[0]) { // 如果s不能被某单词列表组成, 直接返回本身，用逗号拼接
        string res = "";
        for (auto x : s){
            res += x;
            res += ",";
        }
        return res.substr(0 , res.size() - 1);
    }

    int i = 0;
    // 从前往后求解
    while (i < n) {
        int mx = -1; // 记录从i开始，最长可能的长度，需要满足两个条件: 这个前缀出现在单词中，去掉这个前缀，后缀还是能被组成
        // 遍历单词列表
        for (const string& x : words) {
            // 单词长度
            int m = x.length();
            // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
            if (i + m <= n && s.substr(i, m) == x && f[i + m]) {
                mx = max(mx, m);
            }
        }
        // 记录分解方式
        res.push_back(s.substr(i, mx));
        i += mx;
    }
    // 返回分解方式
    return joinString(res , ",");
}

int main() {
    string s;
    getline(cin, s);

    string wordsInput;
    getline(cin, wordsInput);
    vector<string> words;
    size_t start = 0;
    size_t end = wordsInput.find(",");
    while (end != std::string::npos) {
        words.push_back(wordsInput.substr(start, end - start));
        start = end + 1;
        end = wordsInput.find(",", start);
    }
    words.push_back(wordsInput.substr(start, end));

    // 对s split先
    vector<string> asks;
    start = 0;
    end = s.find(",");
    while (end != std::string::npos) {
        asks.push_back(s.substr(start, end - start));
        start = end + 1;
        end = s.find(",", start);
    }
    asks.push_back(s.substr(start, end));

    // 一个个单词去dp
    vector<string> res;
    for (const string& x : asks) {
        res.push_back(solve(x, words));
    }
    cout << joinString(res , ",") << endl;
    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static String joinString(List<String> arr, String s) {
        StringBuilder res = new StringBuilder();
        for (String x : arr) {
            res.append(x).append(s);
        }
        return res.substring(0, res.length() - s.length());
    }

    // 动态规划求解字符串s是否能被某单词列表组成
    // 在有多种拆分情况下，考虑从左到右长度尽量长的单词去切分
    public static String solve(String s, List<String> words) {
        int n = s.length();
        boolean[] f = new boolean[n + 1]; // f[i]表示s[i:]这个后缀能被某单词列表组成
        f[n] = true; // 空串能被某单词列表组成

        for (int i = n; i >= 0; i--) { // 从后往前求解
            for (String x : words) { // 遍历单词列表
                int m = x.length(); // 单词长度
                if (i + m <= n && s.substring(i, i + m).equals(x) && f[i + m]) { // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
                    f[i] = true; // 则s[i:]能被某单词列表组成
                    break;
                }
            }
        }

        // 接下来考虑如何从f这个动态规划数组中拆出具体方案
        List<String> res = new ArrayList<>(); // 记录分解方式
        if (!f[0]) { // 如果s不能被某单词列表组成, 直接返回本身，用逗号拼接
            StringBuilder result = new StringBuilder();
            for (char c : s.toCharArray()) {
                result.append(c).append(",");
            }
            return result.substring(0, result.length() - 1);
        }

        int i = 0;
        // 从前往后求解
        while (i < n) {
            int mx = -1; // 记录从i开始，最长可能的长度，需要满足两个条件: 这个前缀出现在单词中，去掉这个前缀，后缀还是能被组成
            // 遍历单词列表
            for (String x : words) {
                // 单词长度
                int m = x.length();
                // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
                if (i + m <= n && s.substring(i, i + m).equals(x) && f[i + m]) {
                    mx = Math.max(mx, m);
                }
            }
            // 记录分解方式
            res.add(s.substring(i, i + mx));
            i += mx;
        }
        // 返回分解方式
        return joinString(res, ",");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String s = scanner.nextLine();

        String wordsInput = scanner.nextLine();
        List<String> words = new ArrayList<>();
        String[] wordsArray = wordsInput.split(",");
        for (String word : wordsArray) {
            words.add(word);
        }

        // 对s split先
        String[] asksArray = s.split(",");
        List<String> asks = new ArrayList<>();
        for (String ask : asksArray) {
            asks.add(ask);
        }

        // 一个个单词去dp
        List<String> res = new ArrayList<>();
        for (String x : asks) {
            res.add(solve(x, words));
        }
        System.out.println(joinString(res, ","));
    }
}

Python

def solve (s): 
	# 动态规划求解字符串s是否能被某单词列表组成
	# 在有多种拆分情况下，考虑从左到右长度尽量长的单词去切分
	
    n = len(s)
    f = [False] * (n + 1) # f[i]表示s[i:]这个后缀能被某单词列表组成
    f[n] = True  # 空串能被某单词列表组成
    for i in range(n , -1 , -1): # 从后往前求解
        for x in words:# 遍历单词列表
            m = len(x) # 单词长度
            if i + m <= n and s[i : i + m] == list(x) and f[i + m]: # 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
                f[i] = True  # 则s[i:]能被某单词列表组成
                break
    # 以上的思路可以去参考leetcode139
    
    # 接下来考虑如何从f这个动态规划数组中拆出具体方案
    res = [] # 记录分解方式
    if not f[0]: # 如果s不能被某单词列表组成 , 直接返回本身，用逗号拼接
    	return ",".join(s)
    i = 0
    # 从前往后求解
    while i < n:
        mx = -1 # 记录从i开始，最长可能的长度 ， 需要满足两个条件:这个前缀出现在单词中,去掉这个前缀，后缀还是能被组成
        # 遍历单词列表
        for x in words:
            # 单词长度
            m = len(x)
            # 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
            if i + m <= n and s[i : i + m] == list(x) and f[i + m]:
                mx = max(mx , m)
        # 记录分解方式
        res.append("".join(s[i : i + mx]))
        i += mx
    # 返回分解方式
    return ",".join(res)

s = input()
n = len(s)
words = input().split(",")

# 对s split先
asks = s.split(",")
# 一个个单词去dp
res = []
for x in asks:
    x = list(x)
    res.append(solve(x))

print(",".join(res))

JavaScript

let solve = (s, words) => {
    let n = s.length;
    let f = new Array(n + 1).fill(false); // f[i]表示s[i:]这个后缀能被某单词列表组成
    f[n] = true; // 空串能被某单词列表组成

    for (let i = n; i >= 0; i--) { // 从后往前求解
        for (let x of words) { // 遍历单词列表
            let m = x.length; // 单词长度
            if (i + m <= n && s.slice(i, i + m).join("") == x && f[i + m]) { // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
                f[i] = true; // 则s[i:]能被某单词列表组成
                break;
            }
        }
    }

    // 接下来考虑如何从f这个动态规划数组中拆出具体方案
    let res = []; // 记录分解方式
    if (!f[0]) { // 如果s不能被某单词列表组成, 直接返回本身，用逗号拼接
        return s.join(",");
    }

    let i = 0;
    // 从前往后求解
    while (i < n) {
        let mx = -1; // 记录从i开始，最长可能的长度，需要满足两个条件: 这个前缀出现在单词中，去掉这个前缀，后缀还是能被组成
        // 遍历单词列表
        for (let x of words) {
            // 单词长度
            let m = x.length;
            // 如果s[i : i + m]是单词x且s[i + m:]能被某单词列表组成
            if (i + m <= n && s.slice(i, i + m).join("") === x && f[i + m]) {
                mx = Math.max(mx, m);
            }
        }
        // 记录分解方式
        res.push(s.slice(i, i + mx).join(""));
        i += mx;
    }
    // 返回分解方式
    return res.join(",");
};

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    let s = lines[0];
    let words = lines[1].split(",");
    let asks = s.split(",");
    let res = [];
    for (let x of asks) {
        let xArray = x.split("");
        res.push(solve(xArray, words));
    }
    console.log(res.join(","));
});

题目描述

给定一个连续不包含空格的字符串，该字符串仅包含英文小写字母及英文标点符号(逗号、 分号、句号)，同时给定词库，对该字符串进行精确分词。

说明：

精确分词：字符串分词后，不会出现重叠。

即"ilovechina" ,不同词库可分割为",love,china" ，“ilove,china” ,不能分割出现重叠 的",ilove,china", i 出现重叠。

标点符号不成词，仅用于断句

词库：根据外部知识库统计出来的常用词汇例：

dictionary = [", “love”, “china”, “lovechina” , “ilove”]

分词原则：采用分词顺序优先且最长匹配原则 “llovechina”, 假设分词结果[i,ilove,lo,love,ch,china,lovechina],则输出[ilove,china]

错误输出：[i,lovechina], 原因: “ilove” >优先于"lovechina"成词

错误输出：[i,love,china], 原因: “ilove” > "遵循最长匹配原则

输入描述

第一行输入待分词语句 S。

第二行输入中文词库。

字符串 S长度限制： 0 < S.length < 256。

词库长度限制： 1 < length < 100000。

输出描述

按顺序输出分词结果

样例1

输入

ilovechina
i,love,china,ch,na,ve,lo,this,is,the,word

输出

i,love,china

样例2

输入

iat
i,love,china,ch,na,ve,lo,this,is,the,word,beauti,tiful,ful

输出

i,a,t