如果两个字符串的字符一样,但是顺序不一样,被认为是兄弟字符串,问如何迅速匹配兄弟字符串?
首先:接到题目,匹配字符串,这不简单了,遍历嘛。。
方法一:
步骤如下:
1.判断两个字符串的长度是否一样。
2.循环提取第一个字符串的字符去第二个字符串中寻找是否存在?
3.全部都有则是兄弟字符串,其他则不是兄弟字符串。
时间复杂度N*N/2 ,平方级。
额,这算法真的就正确么??????
来看看这种情况:字符串A为aab;字符串B为abc,一看就知道它们是false,那按照上面我写的算法得出的结论却是true。
上面的算法错误的,考虑不周,那以遍历这种思路到底是否能判断兄弟字符串?
能,只要把上面的算法第2步稍微改动一下,改为“2.循环提取第一个字符串的字符去第二个字符串中寻找是否存在?存在则移除第二个字符串中的那个字符。”
好了,遍历思路算是可以解决了这个问题了。
不过嘛,遍历思路的时间复杂度是指数级,太耗时间,性能不好。
方法二:
赋予字符额外的意义。什么意思了,给26个字符依次赋予质数。质数是比较特殊的一堆数字,它们只能被1和本身整除。
给a赋值2、给b赋值3、给c赋值5、给d赋值7、给e赋值11、给f赋值13 等等……
好了,给两个字符串中的所有字符都赋值了,,接着让它们各自相加,如果两个字符串得出的结果是一样的,那它们是兄弟字符串。。
嘎嘎,时间复杂度是常数。性能好了是不????
别太高兴了,这个算法到目前为止也是有问题的,来看看这种情况:bf和ce不是兄弟字符串,按照上面的赋值规律b+f=3+13=16;c+e=5+11=16 ,看吧,明明他们就不是兄弟字符串,但是按照上面的算法就错了。
怎么解决这个问题了?用乘积:每个字符串内部求乘积,相等就是兄弟字符串。
好了,这算法是正确的,但是呢,又有个算法外的问题:字符串相乘及其容易出现结果溢出,说得简单点就是乘积太大了,大于程序语言的内置的整数类型(int、long)所能表示的最大值。这怎么解决?有个比较偏的方法就是用数组来存储乘积。具体方法我不说了,跟本偏文章无关。。。
那怎么解决兄弟字符串的问题???用平方和或者立方和。。。。。既然直接用加法不行,用乘法还会溢出。那换个思路用平方和。。。
b*b+f*f=3*3+13*13=178;c*c+e*e=5*5+11*11=146
看吧它们不是兄弟字符串吧。。。。。
这只是我的算法思路,可能有误,仅供参考。。。。