回文字串(力扣热题HOT100 之 力扣647)java多种方法

简介: 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。

一、题目描述



给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。


具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。


示例 1:

输入:s = "abc"

输出:3

解释:三个回文子串: "a", "b", "c"


示例 2:

输入:s = "aaa"

输出:6

解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

 

提示:

1 <= s.length <= 1000

s 由小写英文字母组成


二、思路讲解及代码实现



1、枚举

       

最容易想到的方法就是枚举出所有子串,然后依次判断它是不是回文字串。

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        if(len <= 1){
            return len;
        }
    //记录回文串的个数
        int count = 0;
    //枚举所有的字串
        for(int i=0; i<len; i++){
            for(int j=i; j>=0; j--){
                if(isHuiwen(s, i, j)){
                    count++;
                }
            }
        }
        return count;
    }
  //判断字串是否回文
    boolean isHuiwen(String s, int i, int j){
        int ii = j;
        int jj = i;
        while(ii<=jj){
            if(s.charAt(ii) != s.charAt(jj)){
                return false;
            }
            ii++;
            jj--;
        }
        return true;
    }
}


时间复杂度:        O(N^3)

空间复杂度:        O(1)


2、中心拓展

       

从中心开始向两端扩展,如果两端的字符不相等,说明不回文。


这里需要注意一个问题:奇数长度的回文串,中心为一个字符;而偶数长度的字符串,中心为两个字符,这需要分开考虑。而其实也可以将这两种情况合并在一个循环内。

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        if(len <= 1){
            return len;
        }
        //回文串的个数
        int count = 0;
        //计算奇数长度的回文串
        for(int i=0; i<len; i++){
            int left = i;
            int right = i;
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){
                count++;
                left--;
                right++;
            }
        }
        //计算偶数长度的回文串
        for(int i=0; i<len-1; i++){
            int j = i+1;
            int left = i;
            int right = j;
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){
                count++;
                left--;
                right++;
            }
        }
        return count;
    }
}


时间复杂度:        O(N^2)

     

空间复杂度:        O(1)

相关文章
|
2天前
|
Java 数据处理 数据安全/隐私保护
Java处理数据接口方法
Java处理数据接口方法
10 1
|
20天前
|
存储 Java 程序员
Java基础的灵魂——Object类方法详解(社招面试不踩坑)
本文介绍了Java中`Object`类的几个重要方法,包括`toString`、`equals`、`hashCode`、`finalize`、`clone`、`getClass`、`notify`和`wait`。这些方法是面试中的常考点,掌握它们有助于理解Java对象的行为和实现多线程编程。作者通过具体示例和应用场景,详细解析了每个方法的作用和重写技巧,帮助读者更好地应对面试和技术开发。
70 4
|
2月前
|
Java API
Java 对象释放与 finalize 方法
关于 Java 对象释放的疑惑解答,以及 finalize 方法的相关知识。
48 17
|
24天前
|
Java 测试技术 Maven
Java一分钟之-PowerMock:静态方法与私有方法测试
通过本文的详细介绍,您可以使用PowerMock轻松地测试Java代码中的静态方法和私有方法。PowerMock通过扩展Mockito,提供了强大的功能,帮助开发者在复杂的测试场景中保持高效和准确的单元测试。希望本文对您的Java单元测试有所帮助。
64 2
|
2月前
|
Java 开发者
在Java多线程编程中,创建线程的方法有两种:继承Thread类和实现Runnable接口
【10月更文挑战第20天】在Java多线程编程中,创建线程的方法有两种:继承Thread类和实现Runnable接口。本文揭示了这两种方式的微妙差异和潜在陷阱,帮助你更好地理解和选择适合项目需求的线程创建方式。
20 3
|
2月前
|
Java 开发者
在Java多线程编程中,选择合适的线程创建方法至关重要
【10月更文挑战第20天】在Java多线程编程中,选择合适的线程创建方法至关重要。本文通过案例分析,探讨了继承Thread类和实现Runnable接口两种方法的优缺点及适用场景,帮助开发者做出明智的选择。
19 2
|
2月前
|
安全 Java
Java多线程通信新解:本文通过生产者-消费者模型案例,深入解析wait()、notify()、notifyAll()方法的实用技巧
【10月更文挑战第20天】Java多线程通信新解:本文通过生产者-消费者模型案例,深入解析wait()、notify()、notifyAll()方法的实用技巧,包括避免在循环外调用wait()、优先使用notifyAll()、确保线程安全及处理InterruptedException等,帮助读者更好地掌握这些方法的应用。
19 1
|
2月前
|
Java 开发者
Java多线程初学者指南:介绍通过继承Thread类与实现Runnable接口两种方式创建线程的方法及其优缺点
【10月更文挑战第20天】Java多线程初学者指南:介绍通过继承Thread类与实现Runnable接口两种方式创建线程的方法及其优缺点,重点解析为何实现Runnable接口更具灵活性、资源共享及易于管理的优势。
34 1
|
2月前
|
Java
在Java多线程编程中,`wait()`和`notify()`方法的相遇如同一场奇妙的邂逅
在Java多线程编程中,`wait()`和`notify()`方法的相遇如同一场奇妙的邂逅。它们用于线程间通信,使线程能够协作完成任务。通过这些方法,生产者和消费者线程可以高效地管理共享资源,确保程序的有序运行。正确使用这些方法需要遵循同步规则,避免虚假唤醒等问题。示例代码展示了如何在生产者-消费者模型中使用`wait()`和`notify()`。
28 1
|
26天前
|
Java Spring
JAVA获取重定向地址URL的两种方法
【10月更文挑战第17天】本文介绍了两种在Java中获取HTTP响应头中的Location字段的方法:一种是使用HttpURLConnection,另一种是使用Spring的RestTemplate。通过设置连接超时和禁用自动重定向,确保请求按预期执行。此外,还提供了一个自定义的`NoRedirectSimpleClientHttpRequestFactory`类,用于禁用RestTemplate的自动重定向功能。
下一篇
无影云桌面