3.31华为软件笔试编程题第3题
输入小写元素组成的字符串str,再输入小写元素组成的需要查找的子串substr(保证子串中的字符至少在str中出现一次)
需要移动游标,以最少的步数找到子串。游标可以向左移动或者向右移动,移动到边界可以循环至另一头。
str长度:[1,1000]; substr长度:[1,100]
in:
aemoyn
amo
0
out:
3
思路:气死我了刚开始以为是贪心算法,每步选择距离最短的下一个index。结果只通过了75%,最后十分钟想通了需要输出总步数最小!!!!所以贪心算法不得行!!!(暴风咆哮)
结果没来得及提交时间就到了,捶胸顿足ing....
贴上代码,递归层数还是挺多的...也不知道能不能ac...
如果有问题请指出,有更好解法请艾特我,谢谢!
#include <bits/stdc++.h> string str,sustr; int len; map< char,vector<int> > mp; int rec(int before,int index, int supos){ if(supos == sustr.size() ) return before; if(sustr[supos] == str[index]) return rec(before, index,supos+1); int res = INT_MAX; char a = sustr[supos]; for(int j=0;j<mp[a].size();j++ ){ int np = mp[a][j]; res = min(res, rec(before+ min(abs(index - np) , abs( len - abs(index-np) )) , np, supos+1)); } return res; } int main(){ //string str,sustr; cin>>str; getchar(); cin>>sustr; getchar(); int index; cin>>index; //cout<< str<<" "<<sustr<<" "<<index<<endl; len = str.size(); for(int i=0;i<len;i++){ mp[ str[i] ].push_back(i); } int res=rec(0, index, 0); cout<<res<<endl; return 0; }