possible sentences_蘑菇街笔试题

Daxong

这题的测试用例输入是个迷。。。

发表于 2019-03-28 16:38:45 回复(0)

浪潮逆转啦

思路讲解和代码实现：

https://blog.csdn.net/Leeycw96/article/details/89336456

发表于 2019-04-16 17:23:39 回复(0)

清雪冰橙

前缀树+dfs。。。

需要吐槽的是：

1. 输入格式问题(我吐了..

2. 输出格式，正向扫描的小伙伴们肯定会wa在题目给的测试样例，需要对所有的结果句子取个反才能A掉.. （为什么题目不描述清楚？

# include<iostream>
(720)#include<cstring>
# include<map>
(747)# include<algorithm>
# include<vector>
(721)# include<cmath>
#include <sstream>
using namespace std;
 
struct tri_node{
    tri_node * children[26];
    bool isWord;
    tri_node(){
        for(int i=0; i<26; ++i)
            children[i] = NULL;
        isWord = false;
    }
};
 
void insert( tri_node* rt, string word ){
    int i=0;
    while(i<word.size()){
        if (rt->children[word[i]-'a']==NULL)
            rt->children[word[i]-'a'] = new tri_node();
        rt = rt->children[word[i]-'a'];
        ++i;
    }
    rt->isWord = true;
}
 
bool search( tri_node * rt, string word ){
    int i=0;
    while(i<word.size()){
        if ( !rt->children[word[i]-'a'] )
            return false;
        rt = rt->children[word[i]-'a'];
        ++i;
    }
    return rt && rt->isWord;
}
 
vector<string> split( string ip, char c ){
    if ( ip.size()==0 || (ip.size()==1 && ip[0]==c) ) return {};
    istringstream  iss(ip);
    vector<string> res;
    string tmp;
    while( getline(iss, tmp, c) ){
        res.push_back(tmp);
    }
    return res;
}
 
void dfs(tri_node* rt , string s, int i, vector<string>&res, string cur){
    string f = "";
    if (i>=s.size() && cur.size()>0){
        cur.pop_back();
        res.push_back(cur);
        return;
    }
    for(int t=i; t<s.size(); ++t){
        f+=s[t];
        if (search(rt, f)){
            // 找到这个单词了
            dfs(rt, s, t+1, res, cur +f+ ' ');
        }
    }
}
 
int main(void){
    int n,m;
    string s, dic;
    getline(cin, s);
    getline(cin,dic);
    s = split(s, '\"')[1];
    vector<string> tmp = split(dic,'\"');
    vector<string> words;
    for(int i=1; i<tmp.size(); i+=2){
        words.push_back(tmp[i]);
    }
    tri_node * rt = new tri_node();
 
    for(auto&word:words)
        insert(rt, word);
     
    vector<string> res;
    dfs(rt, s, 0, res,"");
    reverse(res.begin(), res.end());
     
    cout<<"[";
    for(int i=0; i<res.size(); ++i){
        cout<<res[i];
        if (i+1<res.size())
            cout<<", ";
    }
    cout<<"]"<<endl;
 
 
    return 0;
}

发表于 2020-03-05 23:35:13 回复(0)

lentolove

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine().trim().split("\"")[1];
        String[] split = bf.readLine().trim().split("\"");
        HashSet<String> dic = new HashSet<>();
        for (int i = 0; i < split.length; i++) {
            if (i % 2 != 0) {
                dic.add(split[i]);
            }
        }
        ArrayList<String> ans = new ArrayList<>();
        backtrack(dic, new StringBuilder(), s, ans);
        //下面就是字符串的拼接了..........
        if (ans.size() == 0){
            System.out.println("[]");
            return;
        }

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        for (int i = 0; i < ans.size() - 1; i++){
            String s1 = ans.get(i);
            sb.append(s1.substring(0,s1.length()-1)).append(',').append(" ");
        }
        String s2 = ans.get(ans.size()-1);
        sb.append(s2.substring(0,s2.length()-1)).append(']');
        System.out.println(sb.toString());
    }

    //很标准的回溯算法
    private static void backtrack(HashSet<String> dic, StringBuilder sb, String s, ArrayList<String> list) {
        if (s.isEmpty()) {
            list.add(sb.toString());
            sb.delete(0, sb.length());//组合成功记得清零
            return;
        }
        for (String item : dic) {
            if (s.startsWith(item)) {
                backtrack(dic, sb.append(item).append(" "), s.substring(item.length()), list);
            }
        }
    }
}

发表于 2019-08-21 16:59:29 回复(0)

Python

ElonB

""""
深度优先搜索DFS
"""


def dfs(s, dic, arr, ans):
    if not s:
        ans.append(' '.join(arr))
    for w in dic:
        if s.startswith(w):
            dfs(s[len(w):], dic, arr + (w,), ans)


if __name__ == "__main__":
    s = input().strip()
    s = s[s.index('"') + 1:-1]
    dic = input().strip()
    dic = eval("[" + dic[dic.index('"'):] + "]")
    dic.sort(reverse=True)
    ans = []
    dfs(s, dic, tuple(), ans)
    print('[' + ', '.join(ans) + ']')

发表于 2019-07-16 14:06:25 回复(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)

微雪的早晨

//亂七八糟，不過通過了所有測試用例
import java.util.*;

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

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

        String words = in.nextLine();
        String[] dict;
        int dictBegin = words.indexOf("\"");
        int dictEnd = words.lastIndexOf("\"");
        words = words.substring(dictBegin + 1, dictEnd);
        dict = words.split("\",\"");
        
        StringBuffer sb = new StringBuffer();
        
        System.out.print(f0(f1(s, dict, sb)));
    }
    public static String f0(String s) {
        if (!s.isEmpty()) {
            if (s.lastIndexOf(" ") == (s.length() - 1)) {
                s = s.substring(0, s.length() - 2);
            }
        }
        return "[" + s + "]";
    }

    public static String f1(String s, String[] dict, StringBuffer sb) {
        for (int i = dict.length - 1; i >= 0; i--) {
            if (s.isEmpty()) {
                sb.delete(sb.length() - 1, sb.length());
                sb.append(", ");
                return "";
            }
            if (s.indexOf(dict[i]) != 0) {
                if (i > 0) {
                    continue;
                } else {
                    // i=0
                    if (sb.indexOf(", ") == -1) {
                        sb.delete(0, sb.length());
                    } else {
                        int t = sb.lastIndexOf(", ");
                        sb.delete(t + 2, sb.length());
                    }
                }
            } else {
                sb.append(dict[i] + " ");
                f1(s.substring(dict[i].length()), dict, sb);
            }
        }
        return sb.toString();
    }
}

发表于 2019-04-12 22:05:44 回复(0)

梦秋音

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().replace("s =\"", "").replace("\"", "");
        HashSet dict = new HashSet();
        String[] arr =  sc.nextLine().split("\"");
        for(int i=0;i<arr.length;i++) {
            if(i%2==1) dict.add(arr[i]);
        }
        ArrayList al = new ArrayList();
        String str = "";
        f(str,s,dict,al);
        for(int i=0;i<al.size();i++) {
            String temp = al.get(i);
            al.set(i,temp.substring(0,temp.length()-1));
        }//去掉最后的空格
        System.out.print(al);
    }
    public static void f(String str,String s,HashSet dict,ArrayList al) {
        for(String x:dict) {
            String str_t=str, s_t=s;//防止str，s值被改变
            if(s_t.indexOf(x)==0) {
                str_t = str_t+x+" ";
                s_t = s_t.substring(x.length());
                if(s_t.equals("")) al.add(str_t);
                else f(str_t,s_t,dict,al);//递归调用
            }
        }
    }
}

我不知道为什么只通过了40%，拿着说我不通过的例子在自己的机子上跑，跑出的却是正确的结果。恼火。

编辑于 2019-03-29 21:59:32 回复(0)

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)

犇犇犇犇犇犇犇犇犇犇犇犇

字典树+dfs回溯

import java.util.*;
public class Main{
    static StringBuilder ans = new StringBuilder();
    static List<List<Integer>> res = new ArrayList<>();
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String str1 = in.nextLine();
        String str2 = in.nextLine();
        String s = str1.substring(str1.indexOf('\"')+1,str1.length()-1);
        List<String> words = new ArrayList<>();
        String[] strs = str2.split("\"");
        for(int i = 1; i < strs.length; i+= 2)
            words.add(strs[i]);
        for(int i = 0; i < words.size(); i++){
            insert(words.get(i),root);
        }
        dfs(0,s,root,new ArrayList<Integer>());
        ans.append('[');
        for(int i = 0; i < res.size(); i++){
            StringBuilder ss = new StringBuilder(s);
            for(int j = 0; j < res.get(i).size()-1; j++){
                ss.insert(res.get(i).get(j)+j+1,' ');
            }
            if(i != 0)
                ans.append(", ");
            ans.append(ss.toString());
        }
        ans.append(']');
        System.out.println(ans.toString());
    }
    static void dfs(int pos, String s, Node r, List<Integer> path){
        if(pos == s.length()){
            res.add(0,new ArrayList<>(path));
            return;
        }
        for(int i = pos; i < s.length(); i++){
            r = r.next[s.charAt(i)-'a'];
            if(r == null)
                return;
            if(r.isEnd == 1){
                path.add(i);
                dfs(i+1,s,root,path);
                path.remove(path.size()-1);
            }
        }
        
    }
    static Node root = new Node(-1);
    static class Node{
        int ch;
        int isEnd;
        Node[] next;
        Node(int val){
            ch = val;
            isEnd = 0;
            next = new Node[26];
        }
    }
    static void insert(String str, Node root){
        for(int i = 0; i < str.length(); i++){
            if(root.next[str.charAt(i)-'a'] == null){
                Node p = new Node(str.charAt(i)-'a');
                root.next[str.charAt(i)-'a'] = p;
            }
            root = root.next[str.charAt(i)-'a'];
        }
        root.isEnd = 1;
    }
}

发表于 2021-01-20 10:53:51 回复(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)

大厂offer呢

LeetCode 140 https://leetcode-cn.com/problems/word-break-ii/

发表于 2019-10-27 01:16:06 回复(0)

dyingstraw

import java.util.*;
public class Main{
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s1 = scanner.nextLine().split("=")[1].replaceAll("\"","");
        String s2[] = scanner.nextLine().split("=")[1].replaceAll("[\\[\\]\"]","").split(",");
        // String str = "dogsandcat";
        // String[] dict = new String[]{"dog","dogs","and","sand","cat"};
        String str = s1;
        String[] dict = s2;
        Arrays.sort(dict);
        solution(str,dict,new int[str.length()],0,new ArrayList<>());
        list.sort(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        });
        System.out.println(list);



    }
    public static void solution(String str, String[] dict,int[] select,int st,ArrayList<String> result){

        if (st>=str.length()){
            // System.out.println(result);
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < result.size()-1; i++) {
                stringBuilder.append(result.get(i)+" ");
            }
            stringBuilder.append(result.get(result.size()-1));
            list.add(stringBuilder.toString());
            return;
        }
        for (int i = st+1; i <= str.length(); i++) {

            if (Arrays.binarySearch(dict,str.substring(st,i))>=0){
                result.add(str.substring(st,i));
                solution(str,dict,select,i,result);
                result.clear();
            }
        }

    }
}

递归。。。。有一个案例输出的顺序不对报错了，很迷

发表于 2019-08-08 21:46:15 回复(0)

童心未泯丶

这个不会输入很难受

发表于 2019-04-08 16:21:19 回复(0)

听风雨201809112118346

https://blog.csdn.net/u010155337/article/details/88989089；问题的实现；

发表于 2019-04-03 14:00:19 回复(0)

大卫不加班

目测需要字典树

发表于 2019-03-30 22:11:21 回复(0)

Goooooooooogle201811041748504

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().split("\"")[1];
        String[] temp = sc.nextLine().split("\"");
        String[] dict = new String[temp.length / 2];
        for (int i = 0; i < temp.length / 2; i ++) {
            dict[i] = temp[2 * i + 1];
        }
        ArrayList> list = new ArrayList();
        findSentence(list, s, dict, 0, new ArrayList());
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i ++) {
            ArrayList sentence = list.get(i);
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < sentence.size(); j ++) {
                sb.append(" " + sentence.get(j));
            }
            res[i] = sb.toString().substring(1);
        }
        if (res.length == 2) {
            String str = res[0];
            res[0] = res[1];
            res[1] = str;
        }
        System.out.println(Arrays.toString(res));
    }
    private static void findSentence(ArrayList> list, String s, String[] dict, int idx, ArrayList temp) {
        if (idx >= s.length()) {
            list.add(new ArrayList(temp));
        }
        for (int i = 0; i < dict.length; i ++) {
            String p = dict[i];
            int len = p.length();
            if (idx + len > s.length()) {
                continue;
            }
            for (int j = 0; j < len; j ++) {
                if (p.charAt(j) != s.charAt(idx + j)) {
                    break;
                } else if (j == len - 1) {
                    temp.add(p);
                    idx += len;
                    findSentence(list, s, dict, idx, temp);
                    idx -= len;
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }
}

用的是跟下面链接中类似的回溯算法，但要注意的是这题还要花大量的时间调试输入输出格式，以及输出句子的顺序要跟标准答案一致
https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

发表于 2019-03-29 09:23:32 回复(0)

possible sentences

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题