本文主要是介绍nowcoder possible sentences，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目： possible sentences
题目描述：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]
网址：https://www.nowcoder.com/questionTerminal/371e1d8f234c43eea90d96bd0f214b03
解题思路：
1）处理输入的数据为程序所需要的数据；例如：s =“catsanddog” 处理为 ：catsanddog；第二行dic处理思路和第一行s处理思路一致；
2）找到dic中的字符串在s 中的位置；
3）将字符串的位置和字符串建立映射关系map<int , vector>，因为一个位置可能有多个字符串对应；只匹配dic中字符串在s中第一次匹配的位置。
4）寻找可以将dic中的字符串拼接成为s的所有的集合；
5）输出时候注意输出的格式和位置即可。
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std ;
//4）solveProblem（）是为了寻找所有s的拼接组合
void solveProblem(map<int , vector<string>>& dic , vector<string>& answer , vector<string>& pri , int strSize , int ad , bool& sta)
{if (dic.find(ad) == dic.end())return ;for (auto tmp : dic[ad]){if (ad + tmp.length() == strSize){if (sta)pri.push_back(", ") ;string strtmp = "" ;for (int c_i = 0 ; c_i < answer.size() ; c_i ++)strtmp += (answer[c_i] + " ") ;strtmp += tmp ;pri.push_back(strtmp) ;sta = true ;return ;}answer.push_back(tmp) ;solveProblem(dic , answer , pri , strSize , ad + tmp.length() , sta) ;answer.pop_back() ;}}
int main()
{string str , tmp , getStr;int first , second ;getline(cin , str) ;//第一步，将输入处理为需要的数据例如：s ="catsanddog" , 处理为：catsanddogfirst = str.find("\"") ;second = str.find("\"" , first + 1) ;str = str.substr(first + 1 , second - first - 1) ;vector<string> vecStr ;bool sta = false ;map<int , vector<string>> dic ;getline(cin , getStr) ;int ad ;vector<string> answer , pri ;first = 0 ;first = getStr.find("\"" , first) ;//建立dic 中字符串在 s位置之间的映射以及dic行数据处理为数组while (first != -1){second = getStr.find("\"" , first + 1) ;tmp = getStr.substr(first + 1 , second - first - 1) ;ad = str.find(tmp) ;if (dic.find(ad) == dic.end())dic[ad] = vecStr ;dic[ad].push_back(tmp) ;first = getStr.find("\"" , second + 1) ;}//输出字符串的格式；cout << '[' ;//4）solveProblem（）是为了寻找所有s的拼接组合solveProblem(dic , answer , pri , str.length() , 0 , sta) ;int c_i = pri.size() - 1 ;while(c_i > -1)cout << pri[c_i --] ;cout << ']' << endl ;return 0 ;
}
这篇关于nowcoder possible sentences的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
