Hi All,
I am a beginner to this site and tried to solve the problem . I am using DP but time limit is exceeded on test # 5 . what algorithm shud I use or wat improvements can I do to my code.
///////////////////////////////////////////////////////////
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <fstream>
#include <vector>
using namespace std;
map <char, char> guide;
void initialise()
{
guide['i'] = '1';guide['j'] = '1';guide['a'] = '2';guide['b'] = '2';guide['c'] = '2';guide['d'] = '3';
guide['e'] = '3';guide['f'] = '3';guide['g'] = '4';
guide['h'] = '4';guide['k'] = '5';guide['l'] = '5';guide['m'] = '6';guide['n'] = '6';guide['p'] = '7';
guide['r'] = '7';guide['s'] = '7';guide['t'] = '8';guide['u'] = '8';guide['v'] = '8';guide['w'] = '9';
guide['x'] = '9';guide['y'] = '9';guide['o'] = '0';guide['q'] = '0';guide['z'] = '0';
}
string getcode(string& str)
{
string::iterator it;
string s;
for(it = str.begin();it!=str.end();it++)
{
s.push_back(guide[(*it)]);
}
return s;
}
/*void solve(map <string,vector<string> > m1,string& call)
{
string ret;
typedef string::iterator iter;
iter it;
vector < <string> :: iterator > pos;
typedef map <string,vector <string> > :: iterator t;
for(it=call.begin();it!=call.end();it++)
{
for(iter i = it;i!=call.end();++i)
{
t mt = m1.find(string(it,i));
if(mt != m1.end())
{//we found the 1st word
//must note the position and store in vector
// keep erasing the last one if it is not found
pos.push_back(i);
ret.append(mt->second[0]);
it = i;
it++;
//need to find more
}
}
}
if(ret.length()!=call.length())
cout<<"No Solution";
else
cout<<ret;
}*/
string select(vector < vector<string::iterator> > &book,map <string , vector <string> > &m1,string &str)
{
string ret;
int best = book[0].size();
int pos = 0;
for(int i=1;i<book.size();i++)
{
if(book[i].size()<best)
{
pos = i;
best = book[i].size();
}
}
for(int j = 0;j<best-1;j++)
{
ret.append(m1[string(book[pos][j],book[pos][j+1])][0]);
ret.append(" ");
}
return ret;
}
string solve(map <string , vector <string> > &m1,string &str)
{
int best = 9000000000;
bool no_soln = true;
bool found = false;
typedef string :: iterator iter;
typedef map <string, vector <string> >::iterator it;
vector <string :: iterator> sp;
vector < vector<string::iterator> > db;
sp.push_back(str.begin());
int c = 0;
iter j = sp[c];
while(!(found) && c!=-1)
{
do
{
if (c>best || c==best-1)
break;
j++;
it h = m1.find(string(sp[c],j));
if (h!=m1.end())
{
//we found one word so push it
//cout<<h->second[0]<<" ";
sp.push_back(j);
c++;
}
}while(j!=str.end());
//cout<<c<<" ";
//check whether found or not
if(sp[c] == str.end())
{
if (best>c)
best = c;
cout<<best<<" ";
no_soln = false;
db.push_back(sp);
sp.pop_back();c--;
j = sp[c];
sp.pop_back();c--;
}
else
{j = sp[c];sp.pop_back();c--;}
}
if (!(no_soln))
return select(db,m1,str);
else
return "No solution.";
}
void printing(map <string, vector <string> > &m1)
{
map<string,vector <string> > :: iterator it;
it = m1.begin();
while(it != m1.end())
{
cout<<(*it).first<<" "<<it->second[0]<<"\n";
it++;
}
}
vector <string> readinput(istream &in)
{
vector <string> ret;
string call;
getline(in,call);
while((call.compare("-1"))!=0)
{
map <string , vector<string> > dict;
int words=0;
//getline(in,call);
in>>words;
in.ignore(255,'\n');
string line;
while(words>0)
{
getline(in,line);
dict[getcode(line)].push_back(line);
words--;
}
//printing(dict);
ret.push_back(solve(dict,call));
getline(in,call);
}
return ret;
}
int main()
{
ifstream infile;
infile.open("DATA.in");
ofstream outfile;
outfile.open("DATA.out");
initialise();
vector <string> ans;
ans = readinput(infile);
for(int i=0;i<ans.size();i++)
outfile<<ans[i]<<endl;
/*string m;
getline(cin,m);
cout<<getcode(m);
*/
//getch();
infile.close();
outfile.close();
return 0;
}
