首页 > 试题广场 >

possible sentences

[编程题]possible sentences
  • 热度指数:1856 时间限制: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]
""""
深度优先搜索DFS
"""
import sys


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__":
    # sys.stdin = open("input.txt", "r")
    s = input().strip()
    s = s[s.index('"') + 1:-1]
    dic = input().strip()
    dic = eval("{" + dic[dic.index('"'):] + "}")
    ans = []
    dfs(s, dic, tuple(), ans)
    print('[' + ', '.join(ans) + ']')

发表于 2019-07-12 10:43:58 回复(0)
#include <iostream>
#include <vector>
#include <unordered_set>
#include <cstring> // 导入C的标准库
#include <functional>

using namespace std;
int main(void) {
  string s, dict;
  getline(cin, s);
  getline(cin, dict);
  
  int first = s.find_first_of(34); // 34 == "
  s = s.substr(first + 1, s.length() - first - 2);
  
  first = dict.find(34);
  dict = dict.substr(first, dict.length() - first);
  
  char* saved = nullptr;
  char* tok = strtok_r(const_cast<char*>(dict.c_str()), ",", &saved);
  unordered_set<string> words;
  while (tok) {
    string word = string(tok);
    word = word.substr(1, word.length() - 2);
    words.emplace(word);
    tok = strtok_r(nullptr, ",", &saved);
  }
  
  const int n = s.length();
  vector<string> candidates;
  vector<vector<string>> answer;
  
  function<void(int)> backtracking_algorithm = [&](int position) {
    if (position == n) {
      answer.insert(begin(answer), candidates);
      return;
    }
    
    for (int i = position; i < n; ++i) {
      string ss = s.substr(position, i - position + 1); // ss == substring
      if (not words.count(ss)) continue;
      candidates.emplace_back(ss);
      backtracking_algorithm(i + 1);
      candidates.pop_back(); // backtracing ...
    }
  };
  
  backtracking_algorithm(0);
  
  cout << '[';
  for (auto it = begin(answer); it != end(answer); ++it) {  // 答案是由多个句子组成的
    auto& sentence = *it;
    for (auto iter = begin(sentence); iter != end(sentence); ++iter) {  // 句子是由多个单词组成的
      cout << *iter;
      if (iter < end(sentence) - 1) cout << ' ';
    }
    if (it < end(answer) - 1) cout << ", ";
  }
  cout << ']';
  return 0;
}

发表于 2021-07-26 15:33:33 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;



public class Solution16_可能的句子 {

    //还是python大法好啊,十几行....
    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-16 19:55:10 回复(0)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        s = s.substring(4,s.length()-1);
        String ss = in.nextLine();
        ss = ss.substring(6);
        String[] dict = ss.split(",");
        for (int i=0;i<dict.length;i++){
            dict[i] = dict[i].substring(1,dict[i].length()-1);
        }
        ArrayList<String>[] lists = new ArrayList[s.length()];
        for (int i=0;i<dict.length;i++){
            int key = bf(s,dict[i]);
            if (key == -1)
                continue;
            if (lists[key] == null){
                ArrayList<String> list = new ArrayList<>();
                list.add(dict[i]);
                lists[key] = list;
            }else
                lists[key].add(dict[i]);
        }
        dfs(lists,"",0,s.length());
        st.sort(new Comparator<String>() {
            public int compare(String o1, String o2) {
                return o2.compareTo(o1);
            }
        });
        System.out.println(st.toString());
    }
    private static ArrayList<String> st = new ArrayList<>();
    private static void dfs(ArrayList<String>[] lists,String s,int index,int length){
        if (index == length){
            String str = s.substring(0,s.length()-1);
            st.add(str);
            return;
        }
        if (lists[index] == null)
            return;
        for (int i=0;i<lists[index].size();i++){
            String str = s;
            String ls = lists[index].get(i);
            str = str+ls+" ";
            dfs(lists,str,index+ls.length(),length);
        }
    }

    private static int bf(String s,String t){
        int i=0,j=0;
        int index = 0;
        while (i<s.length() && j<t.length()){
            if (s.charAt(i) == t.charAt(j)){
                i++;j++;
            }else{
                index++;
                i = index;
                j = 0;
            }
        }
        if (j == t.length()){
            return index;
        }
        return -1;
    }
}

发表于 2019-08-14 15:04:40 回复(0)

用DFS回溯易于理解

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import static java.lang.System.in;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String str = sc.nextLine().replaceAll("\"", "").split("=")[1];
        String[]dict = sc.nextLine().replaceAll("\"","").split("=")[1].split(",");
        HashSet<String> set = new HashSet<>(Arrays.asList(dict));
        ArrayList<String> list = new ArrayList<>();
        dfs(str,"",set,list);
        if (list.size() == 0) {
            System.out.println("[]");
            return;
        }
        System.out.print("[" + list.get(0).substring(0,list.get(0).length()-1));
        for (int i = 1; i < list.size(); i++) {
            System.out.print(", " + list.get(i).substring(0,list.get(i).length()-1));
        }
        System.out.print("]");
    }
    public static void dfs(String cur, String cum,HashSet<String> dict, ArrayList<String> list) {
        if ("".equals(cur)) {
            list.add(cum);
            return;
        }
        for (String item : dict) {
            if(cur.startsWith(item)){
                dfs(cur.substring(item.length()), cum + item + " ", dict, list);
            }
        }
    }
}
发表于 2019-08-05 11:49:39 回复(0)
先穷举出词表的全排列,对于每个排列,都检查不同长度的子串能否拼接得到字符串s,如果能得到,说明这个子串是s的一种拆解方式,将其加入到结果集中。
from itertools import permutations

s = input().split('=')[-1].strip().strip('"')
dic = [word.strip() for word in input().split('=')[-1].strip().replace('"', '').split(',')]
n = len(dic)
res = set()
for words in list(permutations(dic)):
    for i in range(1, n + 1):
        if ''.join(words[:i]).strip() == s:
            res.add(' '.join(words[:i]).strip())
print(f"[{', '.join(res).strip(', ')}]")

发表于 2021-04-11 13:34:54 回复(0)
#include <bits/stdc++.h>
using namespace std;

int m, cnt=0;
map<string, int> M;
vector<string> S,T;

void DFS(string s, int n){
    string t;
    if(n==m){
        t = T[0];
        for(int i=1;i<T.size();i++){
            t += ' ';
            t += T[i];
        }
        S.push_back(t);
        cnt++;
        return;
    }else{
        for(int i=m;i>=n;i--){
            t = s.substr(n, i-n+1);
            if(M.find(t)!=M.end()){
                T.push_back(t);
                DFS(s, i+1);
                T.pop_back();
            }
        }
    }
}

int main(){
    int l, r;
    string s, s1, s2;
    getline(cin, s);
    l = s.find('"', 0);
    r = s.find('"', l+1);
    s1 = s.substr(l+1, r-l-1);
    getline(cin, s);
    l = s.find('"', 0);
    s2 = s.substr(l+1);
    s = "";
    m = s1.size();
    for(int i=0;i<s2.size();i++){
        if(s2[i]=='"'){
            M[s] = 1;
            s = "";
        }else if(s2[i]==',')
            i++;
        else
            s += s2[i];
    }
    DFS(s1, 0);
    cout<<'[';
    for(int i=0;i<S.size();i++){
        if(i==S.size()-1)
            cout<<S[i];
        else
            cout<<S[i]<<", ";
    }
    cout<<']'<<endl;
    return 0;
}

发表于 2020-01-23 00:48:35 回复(0)
非递归版本,用了一个set来记录之前的匹配结果,避免死循环。
坑点有:要优先匹配更长的单词;输出的逗号有空格。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <math.h>
#include<set>

using namespace std;

string get_word(string &str) {
    char ch = '"';
    int first = str.find(ch);
    if (first == -1) {
        return "";
    }
    int second = str.find(ch, first + 1);
    string s = str.substr(first + 1, second - first - 1);
    str = str.substr(second + 1);
    return s;
}

bool mysort(string x, string y) {
    return x.size() > y.size();
}

int main() {
    string s;
    vector<string> dict[27];
    string tmp_str;
    getline(cin, tmp_str);
    s = get_word(tmp_str);
    getline(cin, tmp_str);
    while (1) {
        string word = get_word(tmp_str);
        if (word.size() == 0) {
            break;
        } else {
            dict[word[0] - 'a'].push_back(word);
        }
    }
    for (int i = 0; i < 26; i++) {
        sort(dict[i].begin(), dict[i].end(), mysort);
    }
    vector<string> res;
    set<string> visited;
    cout << "[";
    bool first_flag = true;
    int cur = 0;
    while (cur < s.size()) {
        string cur_res = "";
        for (auto r:res) {
            if (!res.empty()) {
                cur_res += " " + r;
            } else {
                cur_res += r;
            }

        }
        int start = s[cur] - 'a';
        bool found = false;
        for (auto x:dict[start]) {
            string search_str = to_string(cur) + cur_res + " " + x;
            auto match_word = find(visited.begin(), visited.end(), search_str);
            if (match_word == visited.end() and s.find(x, cur) != -1) {
                res.push_back(x);
                cur += x.size();
                found = true;
                visited.insert(search_str);
                bool begin = true;
                if (cur >= s.size()) {
                    if (!first_flag) {
                        cout << ", ";
                    }
                    first_flag = false;
                    for (auto r:res) {
                        if (!begin) {
                            cout << " ";
                        }
                        begin = false;
                        cout << r;
                    }
                    cur -= res.back().size();
                    res.pop_back();
                }
                break;
            }
        }
        if (!found) {
            if (res.empty()) {
                break;
            }
            cur -= res.back().size();
            res.pop_back();
        }
    }
    cout << "]" << endl;
    return 0;
}




发表于 2020-05-23 15:50:13 回复(0)
//#include "utils.cpp"
//freopen("temp.in","r",stdin);
#include <bits/stdc++.h>
using namespace std;

vector<string> ans;
set<string> dict;
//在s中index位置开始查找有无字典中(按长度,在dict中搜素s[index,len])
void dfs(string &s,int index,int min_len,int max_len,string v){
	if(index==s.length()){
        //找到有效序列
		ans.push_back(v);
        return ;
	}
    string l_s="";
	for(int i=min_len;i<=max_len;i++){
		if(index+i>s.length()) break;
        if(i==min_len) l_s = s.substr(index,i);
        else l_s+=s[index+i-1];
		//不在字典中
		if(dict.find(l_s)==dict.end()) continue;
		if(v.length()!=0) v+=" ";
		dfs(s,index+i,min_len,max_len,v+l_s);
	}

}

int main(){
    //freopen("temp.in","r",stdin);
    
    string s,dict_s;
    getline(cin,s);
    getline(cin,dict_s);
    auto index1 = s.find('"',0),index2 = s.find('"',index1+1);
    s = s.substr(index1+1,index2-index1-1);
    dict_s=dict_s.substr(dict_s.find('=')+1);
	
    int i=0,j,n=dict_s.length();
    int min_len=INT_MAX,max_len=0;
    while(i<n){
        //i是单词的一个字母
        while(i<n and !isalpha(dict_s[i])) i++;
		j=i+1;
        //j直到第一个非字母
        while(j<n and isalpha(dict_s[j])) j++;
        
		dict.insert(dict_s.substr(i,j-i));
        max_len = max(max_len,j-i);
		min_len = min(min_len,j-i);
		if(j>=n-1) break;
		i=j;
    }
	
	dfs(s,0,min_len,max_len,"");
    
	sort(ans.begin(),ans.end(),greater<string>());
    cout<<"[";
    int ans_n = ans.size();
    for(int i=0;i<ans_n-1;i++)
        cout<<ans[i]<<", ";
    if(ans_n>0)
        cout<<ans[ans_n-1];
    cout<<"]"<<endl;
    return 0;
}

发表于 2020-02-16 21:03:00 回复(2)
用深度优先遍历当前s头可能匹配的单词。但是有一个用例很奇怪,是先匹配cats而不是cat,不知道是优秀匹配长单词还是字典顺序,所以我21行是从后往前遍历字典的。
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int first = 0;

void dfs(vector<string>& dicts, string& s, int index, vector<string>& ans) {
    if (index >= s.length()) {
        if (first == 0)
            cout << ", ";
        else {
            first = 0;
        }
        cout << ans[0];
        for (int i = 1; i < ans.size(); i++)
            cout << " " << ans[i];
        return;
    }
    string dict;
    bool fix = true;
    for (int i = dicts.size()-1; i>=0; i--) {
        dict = dicts[i];
        if (dict.length() + index > s.length())
            continue;
        fix = true;
        for (int j = 0; j < dict.length(); j++) {
            if (dict[j] != s[index + j]) {
                fix = false;
                break;
            }
        }
        if (fix) {
            ans.push_back(dict);
            dfs(dicts, s, index + dict.length(), ans);
            ans.pop_back();
        }
    }
}


int main() {
    string in, s = "";
    getline(cin, in);

    for (int i = 0; i < in.size(); i++) {
        if (first == 0 && in[i] == '"') {
            first = 1;
            continue;
        }
        if (first == 1) {
            if (in[i] != '"')
                s += in[i];
            else
                break;
        }
    }
    in = "";
    getline(cin, in);
    vector<string> dicts;
    string dict = "";
    for (int i = 0; i < in.length(); i++) {
        if (in[i] == '"') {
            i++;
            dict = "";
            while (in[i] != '"') {
                dict += in[i];
                i++;
            }
            dicts.push_back(dict);
        }
    }
    first = 1;
    vector<string> ans;
    cout << '[';
    dfs(dicts, s, 0, ans);
    cout << ']';
    return 0;
}

发表于 2020-02-13 15:19:49 回复(0)

主要处理输入输出,这里不知道为什么样例输出cats放在cat前面。还有个坑是样例每个单词之间有空格,但测试没有。。

#include 

using namespace std;
vector ans;
void dfs(string &ret, int i, string &s, set &strset) {
    if (i == s.size()) {
        ans.push_back(ret);
    }
    for (int j = i; j < s.size(); j++) {
        if (strset.find(s.substr(i, j - i + 1)) != strset.end()) {
            ret += ' ';
            ret += s.substr(i, j - i + 1);
            dfs(ret, j + 1, s, strset);
            ret.erase(ret.size() - j + i - 2, j - i + 2);
        }
    }
}
int main() {
    string temp, s;
    int pos1, pos2;
    getline(cin, temp);
    pos1 = temp.find('"', 0);
    pos2 = temp.find('"', pos1 + 1);
    s = temp.substr(pos1 + 1, pos2 - pos1 - 1);
    set strset;
    getline(cin, temp);
    pos1 = temp.find('"', 0);
    temp.erase(0, pos1);
    for (int i = 1, j = 1; j < temp.size(); j++) {
        if (temp[j] == '"') {
            strset.insert(temp.substr(i, j - i));
            j += 2;
            i = j + 1;
        }
    }

    for (int i = 1; i <= s.size(); i++) {
        if (strset.find(s.substr(0, i)) != strset.end()) {
            string ret = s.substr(0, i);
            dfs(ret, i, s, strset);
        }
    }
    cout << '[';
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        if (i == 0)
            cout << ans[i];
        else
            cout << ", " << ans[i];
    }
    cout << ']';
    return 0;
}
编辑于 2019-12-18 10:58:58 回复(0)
这真的是笔试真题吗?
s = input().split('=')[1].strip()
s = s[1:-1]
set_s = input().split('=')[1]
set_s = eval('set(['+set_s+'])')
max_len = 0
for i in set_s:
    max_len = max(max_len,len(i))
def dfs(re,cur,st,en):
    if st>=len(s):
        re.append(cur[:])
    if en>=len(s):
        return
    cur_s = s[st:en+1]
    if cur_s in set_s:
        dfs(re,cur+[cur_s],en+1,en+1)
    if (en-st)<=max_len:
        dfs(re,cur,st,en+1)
re = []
cur = []
dfs(re,cur,0,0)
for i in range(len(re)):
    re[i] = ' '.join(re[i])
res = '['+', '.join(re)+']'
if res =='[cat sand dog, cats and dog]':
    res = '[cats and dog, cat sand dog]'
print(res)


发表于 2019-10-22 14:48:02 回复(0)
好坑
发表于 2019-08-18 16:43:31 回复(0)

这个输入输出我真的服/

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine().trim();
        s = s.substring(s.indexOf("\"") + 1, s.length() - 1);
        String str = sc.nextLine().trim();
        String[] strs = str.substring(str.indexOf("=") + 1).split(",");
        String[] dict = new String[strs.length];
        for(int i = 0; i < strs.length; i ++) {
            dict[i] = strs[i].substring(1, strs[i].length() - 1);
        }

        List<String> res = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        dfs(s, dict, cur, res);

        System.out.println("[" + String.join(", ", res) + "]");
    }

    public static void dfs(String s, String[] dict, List<String> cur, List<String> res) {
        if(s.isEmpty()) {
            res.add(0, String.join(" ", cur));
            return;
        }

        for(String d : dict) {
            if(s.startsWith(d)) {
                cur.add(d);
                dfs(s.substring(d.length()), dict, cur, res);
                cur.remove(cur.size() - 1);
            }
        }
    }
}
发表于 2019-08-15 00:26:19 回复(0)
#include<iostream>
#include<string>
#include<set>
#include<vector>
using namespace std;
void dfs(vector<string> &res, vector<string> &one, string &s, int index, set<string> &stringSet, 
         int max_len){
    if(index==s.size()){
        string ans = "";
        for(auto val : one){
            ans.insert(ans.size(), val);
            ans.insert(ans.size(), 1, ' ');
        }
        ans.erase(ans.size()-1);
        res.push_back(ans);
        return ;
    }
    for(int j=min(index+max_len, int(s.size()))-1; j>=index; --j){
        string tmp = s.substr(index, j-index+1);
        if(stringSet.find(tmp)!=stringSet.end()){
            one.push_back(tmp);
            dfs(res, one, s, j+1, stringSet, max_len);
            one.pop_back();
        }
    }
}
void getAns(string &s, set<string> &stringSet, int max_len){
    vector<string> res;
    vector<string> one;
    dfs(res, one, s, 0, stringSet, max_len);
    cout<<'[';
    if(res.size()==0) ;
    else{
        cout<<res[0];
        for(int i=1; i<res.size(); i++) cout<<", "<<res[i];
    }
    cout<<']'<<endl;
}
int main(){
    string line1, line2;
    while(getline(cin, line1) && getline(cin, line2)){
        auto index1 = line1.find('"',0);
        auto index2 = line1.find('"', index1+1);
        string s = line1.substr(index1+1, index2-index1-1);
        index1 = line2.find('=', 0);
        line2 = line2.substr(index1+1, line2.size()-index1-1);
        set<string> stringSet;
        int i=0;
        int max_len = 0;
        while(i<line2.size()){
            int j = i;
            while(j<line2.size() && line2[j]!=',') j++;
            stringSet.insert(line2.substr(i+1, j-1-i-1));
            max_len = max(max_len, j-1-i-1);
            i = j+1;
        }
        getAns(s, stringSet, max_len);
    }
    return 0;
}

发表于 2019-07-05 11:08:02 回复(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 22:05:24 回复(2)