美文网首页程序员
【算法】字符串移位

【算法】字符串移位

作者: 一口咖啡一口茶 | 来源:发表于2016-01-25 15:30 被阅读275次

    问题:一个字符串可以由另一个字符串移位得到,例如abcd,可以由bcad移位得到。

    问题分析

    这个问题表面上说的是字符串,但是其实更进一步可以理解为两个字符数组的元素是否一致。最简单和直白的方式,无异于用两层循环的方式来进行循环判断。这是常规方案一。

    还有方案二,则是需要用到数据结构,例如,将一个字符串转换成一个set。循环另一个数组,往set中插入数据,如果一直是失败的,则true。有一次插入成功了,则false。

    方案

    如果我们在转换一下思想,字符其实在计算机中的表现,它的实质上也是数字,比如ASCII码中,字符a是可以转换成数字97的,所以两个数组其实只要求元素之间的差的和,如果等于0就可以判断是否相等。
    例如:
    1,2,34 和 2,3,14
    则:

    1-2=-1
    2-3=-1
    3-1=2
    4-4=0
    

    差的和:

    -1+-1+2+0=0
    

    但是,这样只是判断了移位,并没有判断基准位置。比如,1322是可以判断成立的,因此需要增加判断两个数组的乘积是否相等。来判断基准位置是否一致。

    Python 实现

    def test(old,new):
        if len(old) <= 0 or len(new) <= 0 or len(old) != len(new):
            return false;    
        oldArr = map(ord, old)    
        newArr = map(ord, new)    
        total = 0
        newPro = 1
        oldPro = 1  
        for i in xrange(0,len(oldArr)):        
            total += newArr[i] - oldArr[i]
            newPro = newT * newArr[i]
            oldPro = oldT * oldArr[i]    
        if total == 0 and newPro == oldPro:        
            return True    
        else :        
            return False
    
    if __name__ == '__main__':
        print test('13', '22')
    

    C 语言核心实现

    #include<stdio.h>
      
       int test(char[],int,char[],int);
       int main(){
           char old[]={'b','c','a','d'};
           char new[]={'a','b','c','d'};
           int result = test(old,4,new,4);
           printf("%d\n",result);
           return 0;
      }
     
      int  test(char old[],int oldLen,char new[], int newLen) {
          if(oldLen <= 0 || newLen <= 0 || oldLen != newLen){
              return 0;
          }
      
         int total = 0;
         int newPro = 1;
         int oldPro = 1;
         for(int i=0; i<oldLen; i++){
             total += (int)old[i] - (int)new[i];
             newPro = newPro * new[i];
             oldPro = oldPro * old[i];
          }
     
        if(total == 0 && newPro == oldPro){
             return 1;
        }
        return 0;
    }                  
    

    局限

    我所写实现依赖于ASCII码,当如果字符串是Unioncode编码的字符,则就会出现问题。容我有空去研究一下,相处通用得解决方案。如有问题欢迎各位批评指正,不胜感激。

    相关文章

      网友评论

        本文标题:【算法】字符串移位

        本文链接:https://www.haomeiwen.com/subject/nvgrkttx.html