【每日一题Day150】LC1616分割两个字符串得到回文串 | 双指针+贪心

简介: 【每日一题Day150】LC1616分割两个字符串得到回文串 | 双指针+贪心

分割两个字符串得到回文串【LC1616】

给你两个字符串 ab ,它们长度相同。请你选择一个下标,将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串: aprefixasuffix满足 a = aprefix + asuffix ,同理,由 b 可以得到两个字符串 bprefixbsuffix ,满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。

当你将一个字符串 s 分割成 sprefixssuffix 时, ssuffix 或者 sprefix 可以为空。比方说, s = "abc" 那么 "" + "abc""a" + "bc" "ab" + "c""abc" + "" 都是合法分割。

如果 能构成回文字符串 ,那么请返回 true,否则返回 false

注意x + y 表示连接字符串xy

分割点没有判断好 加油

  • 思路

image.png

实现

class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
       return check(a, b) || check(b, a);
    }
    public boolean check(String a, String b){
        int i = 0, j = b.length() - 1;
        while (i < j && a.charAt(i) == b.charAt(j)){
            i++;
            j--;
        }
        return i >= j || isPalindrome(a, i, j) || isPalindrome(b, i, j);
    }
    public boolean isPalindrome(String s, int i, int j){
        while (i < j && s.charAt(i) == s.charAt(j)){
            i++;
            j--;
        }
        return i >= j;
    }
}

复杂度分析


时间复杂度:O ( n )

空间复杂度:O ( 1 )

目录
打赏
0
0
0
0
5
分享
相关文章
C4.
|
9月前
|
C语言中如何通过指针引用字符串
C语言中如何通过指针引用字符串
C4.
107 0
|
9月前
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
70 0
|
9月前
【每日一题Day117】LC1234替换子串得到平衡字符串 | 双指针
【每日一题Day117】LC1234替换子串得到平衡字符串 | 双指针
63 0
|
9月前
|
通过指针引用字符串
通过指针引用字符串
116 1
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
208 4
|
9月前
|
C++程序中的字符串与指针
C++程序中的字符串与指针
96 2
C语言之字符串的连接使用指针和调用函数两种方法
C语言之字符串的连接使用指针和调用函数两种方法
298 0
|
9月前
|
C语言指针与字符串
C语言指针与字符串
62 0
C语言之指针(指针数组以及指针的指针和字符串)
C语言之指针(指针数组以及指针的指针和字符串)
115 0
|
9月前
|
指针与字符串:C语言中的深入探索
指针与字符串:C语言中的深入探索
170 0