面试问题求教 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

面试问题求教

面试问题求教# JobHunting - 待字闺中

y*x2017-04-15 07:04

1 楼

怎样比较两个字符串一样，除了顺序有一个不同。比如：
AAABB 和 ABBAA 是一样的。AB 和BA 是一样的。就是如果头尾相接，它们是一样的。
简单的解法比如：把第一个重复两次，然后看第二个是不是在第一里面。有其他更有
效的算法吗？

s*z2017-04-15 07:04

2 楼

看了三四遍才明白问题是什么
你的解法已经是线性时间了吧

s*32017-04-15 07:04

3 楼

看不明白问题...是palindrome 还是?

b*e2017-04-15 07:04

4 楼

如果是把string看成一个字母的集合，顺序不考虑，可以按第一个string建一个
hashmap 然后便利第二个string

y*g2017-04-15 07:04

5 楼

一帮b读不懂题目还老有人吹老中技术牛逼此版堪忧

o*r2017-04-15 07:04

6 楼

小白试水。
bool operator==(const string& s1, const string& s2) {
if (s1.length() != s2.length()) return false;
string tmp = s1 + s1;
string::size_type pos = tmp.find_first_of(s2);
return pos != string::npos;
}

y*x2017-04-15 07:04

7 楼

就是感觉有点费内存，我重复了第一个字符串。如果字符串很大的话。
sorry for the confusion. I dont know if there is a name for this type
question.
the problem was how to check if two strings are the "same"
here the same is defined as :
the 2nd string can start from any position of the 1st string, then continue
to the end, then catch up the begin. That is: for given s1 and s2, we say s2
"same as" s1
if s2 = s1[n:end] + s1[0:n-1] where n can be any integer from 0 to end and
you certainly dont know this n.

【在 s****z 的大作中提到】