检查一个字符串是另一个旋转无串联 [英] Check if a string is rotation of another WITHOUT concatenating

查看:126
本文介绍了检查一个字符串是另一个旋转无串联的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

有2个字符串,我们如何检查,如果一个是另一个的旋转形式?

例如:你好--- lohel

一个简单的解决方案是通过串联第一个字符串与自己和检查,如果另外一个是的串联的版本。

有没有其他的解决办法呢?

我在想,如果我们可以使用循环链表可能?但我不能够在达成解决方案。

解决方案
  

一个简单的解决办法是通过连接它们并检查是否另一个是的级联版本的子串。

我假设你的意思是串联与自己的第一个字符串,然后检查是否另一种是串联的子串。

这将工作,实际上可以在没有任何拼接完成的。只要使用任何字符串搜索算法搜索第二个字符串中的第一个,当你到达终点,循环返回起点。

例如,使用博耶 - 穆尔的整体算法会为O(n)。

There are 2 strings , how can we check if one is a rotated version of another ?

For Example : hello --- lohel

One simple solution is by concatenating first string with itself and checking if the other one is a substring of the concatenated version.

Is there any other solution to it ?

I was wondering if we could use circular linked list maybe ? But I am not able to arrive at the solution.

解决方案

One simple solution is by concatenating them and checking if the other one is a substring of the concatenated version.

I assume you mean concatenate the first string with itself, then check if the other one is a substring of that concatenation.

That will work, and in fact can be done without any concatenation at all. Just use any string searching algorithm to search for the second string in the first, and when you reach the end, loop back to the beginning.

For instance, using Boyer-Moore the overall algorithm would be O(n).

这篇关于检查一个字符串是另一个旋转无串联的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
相关文章
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆