Return all such possible sentences.
[编程题]possible sentences
- 热度指数：1880 时间限制：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.
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)
java代码-----深搜、双指针
发表于 2019-09-30 14:47:49
回复(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)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
