Google 面试题 | 判断字符串是否可由重复子字符串组成

2024-05-26 22:32

本文主要是介绍Google 面试题 | 判断字符串是否可由重复子字符串组成,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

对于一个非空字符串,判断其是否可由一个子字符串重复多次组成。字符串只包含小写字母且长度不超过10000。

样例1

  • 输入: “abab”
  • 输出: True
  • 样例解释: 输入可由”ab”重复两次组成

样例 2

  • 输入: “aba”
  • 输出: False

样例 3

  • 输入: “abcabcabcabc”
  • 输出: True
  • 样例解释:输入可由”abc”重复四次组成

解题思路

1. 一个简单的思路

枚举子字符串的长度lenSub < len(len为原字符串长度),将原字符串分成多个子字符串,每个子字符串长度为lenSub(由此可见,lenSub整除len),再判断这些子字符串是否全部相等,若全部相等,则返回True,如果对于所有lenSub均不满足该条件,则返回False。时间复杂度为O(len*v(len)),其中v(len)为len的因数个数(因为我们只需要对整除len的lenSub进行进一步判断)。

2. 下面再说一种神奇的方法

由kmp算法中的next数组实现。

  1. 字符串s的下标从0到n-1,n为字符串长度,记s(i)表示s的第i位字符,s(i,j)表示从s的第i位到第j位的子字符串,若i>j,则s(i,j)=””(空串)。

  2. next数组的定义为:next(i)=p,表示p为小于i且满足s(0 , p) = s(i-p , i)的最大的p,如果不存在这样的p,则next(i) = -1,显然next(0) = -1。我们可以用O(n)的时间计算出next数组。假设我们已知next(0),next(1),……,next(i-1) ,现在要求next(i),不妨设next(i-1) = j0,则由next数组定义可知s(0 , j0) = s(i-1-j0 , i-1)。

    • 若s(j0+1) = s(i),则结合s(0 , j0) = s(i-1-j0 , i-1)可知s(0 , j0+1) = s(i - (j0+1) , i),由此可知,next(i)=j0+1。

    • 若s(j0+1)!=s(i)但s(next(j0)+1)=s(i),记j1=next(j0),则s(j1+1)=s(i),由next数组的定义,s(0 , j1) = s(j0 - j1 , j0) = s(i - 1 - j1 , i - 1),即s(0,j1) = s(i - 1 - j1 , i - 1),由假设s(j1+1) = s(i),则s(0 , j1+1) = s(i - (j1+1) , i),故next(i) = j1+1。

    • 同前两步的分析,如果我们能找到一个k,使得对于所有小于k的k0,s(j(k0)+1)!=s(i),但有s(j(k)+1) = s(i),则由next数组的定义可以得到next(i)=j(k)+1,否则需进一步考虑j(k+1) = next(j(k)),如果我们找不到这样的k,则next(i)=-1。

  3. 对于字符串s,如果j满足,0<=j<=n-1,且s(0,j) = s(n-1-j,n-1),令k=n-1-j,若k整除n,不妨设n=mk,则s(0,(m-1)k - 1) = s(k,mk - 1),即s(0,k-1) = s(k,2k-1) = …… = s((m-1)k - 1,mk - 1),即s满足题设条件。故要判断s是否为重复子串组成,只需找到满足上述条件的j,且k整除n,即说明s满足条件,否则不满足。

  4. 利用已算出的next(n-1),令k=n-1-next(n-1),由c可知,若k整除n,且k < n,则s满足条件,否则不满足。上述算法的复杂度可证明为O(n)。

参考代码

参考代码给出了利用next数组求解的代码。来自九章算法答案

public class Solution {public boolean repeatedSubstringPattern(String s) {int l = s.length();int[] next = new int[l];next[0] = -1;int i, j = -1;for (i = 1; i < l; i++) {while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {j = next[j];}if (s.charAt(i) == s.charAt(j + 1)) {j++;}next[i] = j;}int lenSub = l - 1 - next[l - 1];return lenSub != l && l % lenSub ==0;}
}

面试官角度分析

这道题的第一种解法比较简单,考察穷举和字符串处理的能力,给出第一种方法并正确分析时间复杂度基本可以达到hire;如果面试者对KMP算法有了解,可以给出第二种next数组的算法可以达到strong hire。

本文来自九章算法公众号 Google 面试题 | 重复子字符串模式

这篇关于Google 面试题 | 判断字符串是否可由重复子字符串组成的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1005772

相关文章

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1:定义时间段类步骤2:添加时间段步骤3:检查时间段是否有重合步骤4:输出结果示例代码结语作

Java中String字符串使用避坑指南

《Java中String字符串使用避坑指南》Java中的String字符串是我们日常编程中用得最多的类之一,看似简单的String使用,却隐藏着不少“坑”,如果不注意,可能会导致性能问题、意外的错误容... 目录8个避坑点如下:1. 字符串的不可变性:每次修改都创建新对象2. 使用 == 比较字符串,陷阱满

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

IDEA编译报错“java: 常量字符串过长”的原因及解决方法

《IDEA编译报错“java:常量字符串过长”的原因及解决方法》今天在开发过程中,由于尝试将一个文件的Base64字符串设置为常量,结果导致IDEA编译的时候出现了如下报错java:常量字符串过长,... 目录一、问题描述二、问题原因2.1 理论角度2.2 源码角度三、解决方案解决方案①:StringBui

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

C#从XmlDocument提取完整字符串的方法

《C#从XmlDocument提取完整字符串的方法》文章介绍了两种生成格式化XML字符串的方法,方法一使用`XmlDocument`的`OuterXml`属性,但输出的XML字符串不带格式,可读性差,... 方法1:通过XMLDocument的OuterXml属性,见XmlDocument类该方法获得的xm

查询Oracle数据库表是否被锁的实现方式

《查询Oracle数据库表是否被锁的实现方式》本文介绍了查询Oracle数据库表是否被锁的方法,包括查询锁表的会话、人员信息,根据object_id查询表名,以及根据会话ID查询和停止本地进程,同时,... 目录查询oracle数据库表是否被锁1、查询锁表的会话、人员等信息2、根据 object_id查询被