y**x
发帖数: 117 | 1 怎样比较两个字符串一样，除了顺序 有一个不同。 比如：
AAABB 和 ABBAA 是一样的。AB 和BA 是一样的。 就是如果头尾相接，它们是一样的。
简单的解法比如： 把第一个重复两次，然后看第二个是不是在第一里面。有其他更有
效的算法吗？ |
s****z
发帖数: 11 | 2 看了三四遍才明白问题是什么
你的解法已经是线性时间了吧 |
s****3
发帖数: 270 | 3 看不明白问题...是palindrome 还是? |
b*****e
发帖数: 2511 | 4 如果是把string看成一个字母的集合，顺序不考虑，可以按第一个string建一个
hashmap 然后便利第二个string |
y***g
发帖数: 1492 | 5 一帮b读不懂题目 还老有人吹老中技术牛逼 此版堪忧 |
o*******r
发帖数: 73 | 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**x
发帖数: 117 | 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 的大作中提到】
: 看了三四遍才明白问题是什么
: 你的解法已经是线性时间了吧
|
X***9
发帖数: 34 | 8 这个就是典型space v time balance
你这办法就是最优了，strstr是线性的 |
