首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    高效判断回文子串技巧

    今天学习到一个新的技巧来快速判断回文子串:该方法是通过中心扩展来高效判断是否是回文字符串。回文字符串分为奇回文和偶回文,其中奇回文的中心只有一个,偶回文的中心有两个,所以通过遍历中心来左右扩展判断回文字符串。假设字符串的长度为n,那么如果是奇回文,中心个数就是n个;如果是偶回文,中心个数就是n - 1个,那么总共需要遍历的中心个数就是2n - 1个。其中每次遍历中心的left,right分别是i / 2,i / 2 + i mod 2,如果是回文字符串就left--, right++的往左右两边扩散。此方法的时间复杂度是O(N²),因为枚举每个中心需要O(N)的复杂度,每个中心扩展又需要O(N)的复杂度,所以总的时间复杂度是O(N²)

    00
    领券