【算法】字符串移位

问题:一个字符串可以由另一个字符串移位得到,例如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编码的字符,则就会出现问题。容我有空去研究一下,相处通用得解决方案。如有问题欢迎各位批评指正,不胜感激。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 第5章 引用类型(返回首页) 本章内容 使用对象 创建并操作数组 理解基本的JavaScript类型 使用基本类型...
    大学一百阅读 3,734评论 0 4
  • 前言 本文是题主准备面试时记录下的笔记整理而来,稍显粗陋,还请各位撸友勿喷哈! Topic 目录数组字符串链表二叉...
    rh_Jameson阅读 1,822评论 2 63
  • 2016下半年,你们都说我变了,甚至连我自己都有所察觉到自己的变化还蛮大。我好像已经跟自己告别,却不是好好地跟自己...
    唐伟诗阅读 343评论 0 0
  • 觉得一切都是在保佑着的进行,本觉得得力集团进不了,没想到还能那么一个位置,虽然不对口但是满足了,做人不能太贪心。他...
    fangyuanjili阅读 209评论 0 0
  • 这天半夏要去帮朋友带一节晚课,上课的地方离半夏的家有两个小时的路程,晚上半夏没有回家,去了离上课的地方...
    清空妙有阅读 383评论 2 1

友情链接更多精彩内容