java经典问题：连个字符串互为回环变位

本次给大家带来的是关于判断连个字符串是否互为回环变位（Circular Rotaion）的java程序员面试经常出现的题型，给大家做了两种方式的解答，希望能帮助到你。

一般情况下都是笔试或者是直接上机操作，题型一般都是：如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t，那么 s 就被称为 t 的回环变位（circular rotation）。

A string s is a circular rotation of a string t if it matches when the characters are circularly shifted by any number of positions;
e.g., ACTGACG is a circular shift of TGACGAC, and vice versa. Detecting this condition is important in the study of genomic sequences.
Write a program that checks whether two given strings s and t are circular.

关于解答方面，我给在这里给出了2种方式：
解法一：
将s拆分成左右两部分，然后另令s'=右+左，遍历所有情况。如果是回环字符串的话，其中会有 s'=t 的情况。

public static boolean isCircularRotation(String s, String t) {
    if (s.length() != t.length())
      return false;
    int sLen = s.length();
    for (int i = 0; i <= sLen; i++) {
      // 注意subString的后角标的界限
      String sLeft = s.substring(0, i);
      String sRigth = s.substring(i + 1, sLen);
      if ((sRigth + sLeft).equals(t))
        return true;
    }
    return false;
  }

解法二：（巧妙）

public static boolean isCircularRotation_1(String s, String t) {
  return (s.length() == t.length() && (t + t).contains(s));
}

以上就是基本快速的两种解决方式，关于这个问题，再给大家看一篇很详细的判断字符串回环变位解决思路：

如果字符串s中的字符循环移动任意位置之后能够得到另一字符串t，那么s就被称为t的回环变位。例如，ACTGACG 就是 TGACGAC 的一个回环变位，反之亦然。判定这个条件在基因组序列中的研究是十分重要的。编写一个算法检查两个给定的字符串s和t是否互为回环变位。

这是我在《算法（第四版）》里看到的一道练习题 ，当时的第一想法就是遍历字符串 t，从不同的索引位置将字符串t分解成两个子串，交换顺序拼接后再与s相比是否相等。算法如下：

 public static boolean isCircularRotation(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int length = s.length();
    for (int i = 1; i <= length; i++) {
      String left = s.substring(0, i);
      String right = s.substring(i, length);
      if ((right + left).equals(t)) {
        return true;
      }
    }
    return false;
  }

后来看答案，提示说可以用一行代码就能搞定了。当时想了想，感觉不太可能，就作罢了。今天重新开始学习这本书的时候，再次看到这道题，突然有了想法代码如下：

public static boolean isCircularRotation(String s, String t) {
    return s.length() == t.length() && (t + t).contains(s);
  }

解释：如果字符串s和t互为回环变位，则s可分解为“AB”，t可分解为“BA”。那么t与自身拼接后则为“BABA”，显然是会包含s的。这种思路比较巧妙，当然了，自认为算法效率并没有什么提高。

为什么大家都会对这个经典的JAVA问题困惑着？最主要的原因就是解题的思路问题：

容易想复杂的"回环变位"，思路错误，问题就会复杂化，一起来看下经典的误区和最终想明白以后的解法。

题目描述很简单:
如果字符串s重的字符循环移动任意位置之后能够得到另一个字符串t，那么s就被成为s的回环变位（circular rotation） 举例省略…
问题：请编写一个程序检查2个给定的字符串s和t是否互为回环变位。
提示:判断条件只需要一行代码

看到题目当时满脑子想的都是双重循环啊，游标移动啊各种i,j,k……
结果来一句这样的提示，当时我就受不了了，决定去看一下答案….

答案是这样的

(s.length() == t.length()) && (s.concat(s).indexOf(t) >= 0)

乍一看，好像真的可以…顿时鄙视了自己的各种游标循环i,j,k…
（虽然可能底层也是各种循环游标i,j,k,但是别人都实现了的基类直接用明显更省事…）

但是也发现自己对String类的concat函数和indexOf的各种重载不懂

一下是jdk文档的描述

public String concat(String str)将指定字符串连接到此字符串的结尾。
如果参数字符串的长度为 0，则返回此 String 对象。否则，创建一个新的 String 对象，用来表示由此 String 对象表示的字符序列和参数字符串表示的字符序列连接而成的字符序列。

示例： 

 "cares".concat("s") returns "caress"
 "to".concat("get").concat("her") returns "together"

参数：
str - 连接到此 String 结尾的 String。
返回：
一个字符串，它表示在此对象字符后连接字符串参数字符而成的字符。

public int indexOf(String str)返回指定子字符串在此字符串中第一次出现处的索引。返回的整数是
 this.startsWith(str, k)
 为 true 的最小 k 值。 

参数：
str - 任意字符串。
返回：
如果字符串参数作为一个子字符串在此对象中出现，则返回第一个这种子字符串的第一个字符的索引；如果它不作为一个子字符串出现，则返回 -1。

关于这个问题，已经在上文章阐述的非常清楚了，大家如果对此还有任何的疑问，可以在本文下方留言讨论。

赞 (0)

相关推荐

  • Java日期时间字符串和毫秒相互转换的方法

    Java日期时间字符串和毫秒相互转换的方法

    本文内容大多基于官方文档和网上前辈经验总结,经过个人实践加以整理积累,仅供参考. 1.日期时间字符串转换成毫秒 @Test public void test() throws ParseException { String dateTime = "2016-12-31 12:30:45 123"; Calendar calendar = Calendar.getInstance(); calendar.setTime(new SimpleDateFormat("yyyy-MM

  • Java将字符串写入文本文件代码示例

    一.Filewriter与File---将字符串写入文本文件 public static void main(String[] args) { File f=new File("C:\\world.txt");//新建一个文件对象,如果不存在则创建一个该文件 FileWriter fw; try { fw=new FileWriter(f); String str="hello world"; fw.write(str);//将字符串写入到指定的路径下的文件中 fw

  • java8 统计字符串字母个数的几种方法总结(推荐)

    1.统计字符串字母个数(并且保持字母顺序) 比如: aabbbbbbbba喔喔bcab cdabc deaaa 目前我做知道的有5种方式噢,如果你还有更好的,欢迎赐教 //方式1 public static void letterCount1(String s) { s=s.replaceAll(" +", ""); //1,转换成字符数组 char c[]=s.toCharArray(); Map<Character, Integer> tree=ne

  • Java编程实现统计一个字符串中各个字符出现次数的方法

    本文实例讲述了Java编程实现统计一个字符串中各个字符出现次数的方法.分享给大家供大家参考,具体如下: import java.util.Iterator; import java.util.Set; import java.util.TreeMap; public class TreeMapDemo { //统计一个字符串中相应字符出现的次数 public static void main(String[] args) { // System.out.println("我们测试结果:"

  • java随机生成时间字符串的方法

    本文实例为大家分享了java随机生成时间字符串的具体代码,供大家参考,具体内容如下 package com.wechat.utils; import java.text.SimpleDateFormat; import java.util.Date; /** * Created by hexun on 2017/2/4. */ public class RandTimeUtils { /** * 生成随机时间 * @param beginDate * @param endDate * @retu

  • java字符串与日期类型转换的工具类

    常用的字符串转date,和日期转字符串的方法,具体内容如下 package com.cq2022.zago.base.util; import java.text.DateFormat; import java.text.ParseException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.GregorianCalendar; import javax.xml.datatype.Dat

  • 多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法原理及Java实现代码

    多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题.一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的.该算法广泛应用于关键字过滤.入侵检测.病毒检测.分词等等问题中.多模问题一般有Trie树,AC算法,WM算法等等. 背景 在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 for (String document : d

  • java实现时间与字符串之间转换

    本文实例为大家分享了java实现时间与字符串之间转换的具体代码,供大家参考,具体内容如下 1. long字符串转换成yyyy-MM-dd HH:mm:ss格式输出 import java.text.SimpleDateFormat; import java.util.Date; //将long字符串转换成格式时间输出 public class LongToString { public static void main(String argsp[]){ String time="12560061

  • java经典问题：连个字符串互为回环变位

    本次给大家带来的是关于判断连个字符串是否互为回环变位(Circular Rotaion)的java程序员面试经常出现的题型,给大家做了两种方式的解答,希望能帮助到你. 一般情况下都是笔试或者是直接上机操作,题型一般都是:如果字符串 s 中的字符循环移动任意位置之后能够得到另一个字符串 t,那么 s 就被称为 t 的回环变位(circular rotation). A string s is a circular rotation of a string t if it matches when

  • Java实现查找当前字符串最大回文串代码分享

    先看代码 public class MaxHuiWen { public static void main(String[] args) { // TODO Auto-generated method stub String s = "abb"; MaxHuiWen(s); } //1.输出回文串 public static void MaxHuiWen(String s){ //存储字符串的长度 int length = s.length(); //存储最长的回文串 String M

  • java中利用栈实现字符串回文算法

    问题 给定一个由多个a和b组成的字符串数组,字符串中有一个特殊的字符X,位于字符串的正中间,例如(aaaabbbbXabaabbbb),如何判定该字符串是否回文 简单算法 定义两个下标分别指向字符串的头和尾,每次比较两个下标位置的值是否相等,如果不相等,那么输入的 字符串不是回文,如果相等,左边的下表加1,右边的下表减1,重复上述步骤直至两个下标都指向字符串的正中间或者确定字符串不是回文 /** * 判断字符串是否是回文 */ public int isPalindrome(String inp

  • Java经典面试题最全汇总208道(二)

    目录 前言 53.concurrentHashMap和HashTable有什么区别 54.HasmMap和HashSet的区别 55.请谈谈 ReadWriteLock 和 StampedLock 56.线程的run()和start()有什么区别? 57.为什么我们调用 start() 方法时会执行 run() 方法,为什么我们不能直接调用 run() 方法? 58.Synchronized 用过吗,其原理是什么? 59.JVM 对 Java 的原生锁做了哪些优化? 60.为什么 wait(),

  • Java经典面试题最全汇总208道(一)

    目录 前言 1.JDK 和 JRE 有什么区别? 2.== 和 equals 的区别是什么? 3.final 在 java 中有什么作用? 4.java 中的 Math.round(-1.5) 等于多少? 5.String 属于基础的数据类型吗? 6.String str="i"与 String str=new String(“i”)一样吗? 7.如何将字符串反转? 8.String 类的常用方法都有那些? 9.new String("a") + new Strin

  • Python回文字符串及回文数字判定功能示例

    本文实例讲述了Python回文字符串及回文数字判定功能.分享给大家供大家参考,具体如下: 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.回文数字也是如此. python2代码如下: def huiwen(s): s1=str(s) if s1==''.join(reversed(s1)): return True else: return False 运行结果: >>> huiwen('abccba') True >>> huiwen('abc')

  • Java中多媒体文件上传及页面回显的操作代码

    文件上传页面 <%@ page language="java" contentType="text/html; charset=UTF-8" pageEncoding="UTF-8"%> <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"&

  • Java经典面试题最全汇总208道(五)

    目录 前言 152.什么是 YAML? 153.如何使用 Spring Boot 实现分页和排序? 154.如何使用 Spring Boot 实现异常处理? 155.单点登录 156.Spring Boot比Spring多哪些注解 157.打包和部署 158.Spring Boot如何访问不同的数据库 159.查询网站在线人数 160.easyExcel如何实现 161.什么是 Swagger?你用 Spring Boot 实现了它吗? 162.数据库的三范式是什么? 163.一张自增表里面总共

  • Java经典面试题最全汇总208道(四)

    目录 前言 126.Spring 框架中的单例 Beans 是线程安全的么? 127.请解释 Spring Bean 的自动装配? 129.什么是 Spring Batch? 130.spring mvc 和 struts 的区别是什么? 131.请举例解释@Required 注解? 132.Spring常用注解 133.项目中是如何实现权限验证的,权限验证需要几张表 134.谈谈controller,接口调用的路径问题 135.如何防止表单重复提交 136.Spring中都应用了哪些设计模式

  • Java经典面试题最全汇总208道(三)

    目录 前言 websocket应用的是哪个协议 106.说一下 tcp 粘包是怎么产生的? 107.请列举出在 JDK 中几个常用的设计模式? 108.什么是设计模式?你是否在你的代码里面使用过任何设计模式? 110.在 Java 中,什么叫观察者设计模式(observer design pattern)? 111.使用工厂模式最主要的好处是什么?在哪里使用? 112.请解释自动装配模式的区别? 113.举一个用 Java 实现的装饰模式(decorator design pattern)?它是

随机推荐