首页 > 试题广场 >

possible sentences

[编程题]possible sentences

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

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.

输入描述:

s ="catsanddog"
dict ="cat", "cats", "and", "sand", "dog"

输出描述:

[cats and dog, cat sand dog]

示例1

输入

s ="catsanddog"
dict ="cat","cats","and","sand","dog"

输出

[cats and dog, cat sand dog]

算法知识视频讲解

Java

法国红酒ecnu

用回溯法。其实也不算多难的题。当然了这个题的输入输出实在太扯了，一定要注意substring的索引号别搞错了。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String dict = sc.nextLine();

        s = s.substring(s.indexOf('\"') + 1, s.lastIndexOf('\"'));
        dict = dict.substring(dict.indexOf('=') + 1);
        String[] dictArr = dict.split(",");
        Set<String> set = new HashSet<>();
        for (String e: dictArr){
            set.add(e.substring(e.indexOf('\"') + 1, e.lastIndexOf('\"')));
        }

        List<List<String>> ans = new ArrayList<>();
        List<String> combine = new ArrayList<>();
        traceback(s, 0,0, set, ans, combine);

        List<String> printAns = new ArrayList<>();
        for (List<String> li: ans) {
            StringBuilder sbd = new StringBuilder();
            for (String w: li){
                sbd.append(w).append(" ");
            }
            sbd.deleteCharAt(sbd.length()-1);
            printAns.add(sbd.toString());
        }
        System.out.println(printAns);
    }

    static void traceback(String s, int start, int pt, Set<String> set, List<List<String>> ans, List<String> combine){
        if (pt == s.length()){
            if (set.contains(s.substring(start))){
                combine.add(s.substring(start));
                ans.add(new ArrayList<>(combine));
                combine.remove(combine.size()-1);
            }
            return;
        }
        traceback(s, start,pt+1, set, ans, combine);
        if (set.contains(s.substring(start, pt+1))){
            combine.add(s.substring(start, pt+1));
            traceback(s, pt+1, pt+1, set, ans, combine);
            combine.remove(combine.size()-1);
        }
    }
}

发表于 2021-07-30 13:31:29 回复(0)

Java

温-wjw

import java.util.*;
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().split("=")[1].replace("\"", "");
        String[] dict = sc.nextLine().split("=")[1].replace("\"", "").split(",");
        findSentences(s, dict, "");
        Collections.reverse(res);
        System.out.print(res.toString());
    }
 
    public static List<String> res = new ArrayList<>();
    public static void findSentences(String s, String[] dict, String sentence){
        //结束条件：s.length == 0
        if ("".equals(s) || s.length() == 0){
            res.add(sentence.substring(1));
            return ;
        }
        //将首字母相同的抽取出来
        List<String> firstWord = new ArrayList<>();
        for (String d : dict) {
            if (d.charAt(0) == s.charAt(0)){
                firstWord.add(d);
            }
        }
        //遍历匹配，匹配成功则删除
        for (String word : firstWord) {
            if (s.contains(word)){
                //删除，加入半成品句子，进入下一次递归
                findSentences(s.replace(word, ""), dict, sentence + " " + word);
            }
        }
    }
}

java35行，思路是遍历首字母相同的单词，直接replace(word, "")，不断重复即可

万万没想到还对顺序有要求？

编辑于 2020-07-12 03:50:11 回复(0)

Java

chasein

分享一下解题思路，感觉递归处的代码有问题，但是还是通过所有测试用例了，欢迎指正

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

public class Main {
    private static List<List<String>> ret = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            String str = sc.nextLine();
            String dict = sc.nextLine();

            int sBegin = str.indexOf('\"');
            int sEnd = str.lastIndexOf('\"');
            str = str.substring(sBegin + 1, sEnd);

            int dictBegin = dict.indexOf('\"');
            int dictEnd = dict.lastIndexOf('\"');
            dict = dict.substring(dictBegin + 1, dictEnd);
            String[] dicts = dict.split("\",\"");
            List<String> list = new ArrayList<>();
            getSentences(str, dicts, list);
            System.out.println(format(ret));
        }

    }

    static String format(List<List<String>> ret){
        StringBuilder sb = new StringBuilder();
        for (int i = ret.size() - 1; i >= 0; --i){ //此处还必须倒着输出
            if (i != 0){
                for (int j = 0; j < ret.get(i).size(); ++j){
                    if (j != ret.get(i).size() - 1){
                        sb.append(ret.get(i).get(j) + " ");
                    }else {
                        sb.append(ret.get(i).get(j) + ", ");
                    }
                }
            }else {
                for (int j = 0; j < ret.get(i).size(); ++j){
                    if (j != ret.get(i).size() - 1){
                        sb.append(ret.get(i).get(j) + " ");
                    }else {
                        sb.append(ret.get(i).get(j));
                    }
                }
            }

        }
        sb.append(']');
        sb.insert(0, '[');
        return sb.toString();
    }

    static void getSentences(String str, String[] dicts, List<String> list) {
        if (str.isEmpty()) {
            ret.add(new ArrayList<>(list));
        }
        for (int i = 0; i < dicts.length; ++i) {
            if (str.indexOf(dicts[i]) != 0) {
                if (i == dicts.length - 1) {
                    list.clear();
                }
            } else {
                list.add(dicts[i]);
                getSentences(str.substring(dicts[i].length()), dicts, list);
            }
        }
    }
}

编辑于 2019-06-21 09:02:37 回复(0)