编程之法:面试和算法心得(回文判断)

时间:2022-10-03 16:45:26

内容全部来自编程之法:面试和算法心得一书,实现是自己写的使用的是java

题目描述

回文,英文palindrome,指一个顺着读和反过来读都一样的字符串,比如madam、我爱我,这样的短句在智力性、趣味性和艺术性上都颇有特色,中国历史上还有很多有趣的回文诗。

那么,我们的第一个问题就是:判断一个字串是否是回文?

分析与解法

回文判断是一类典型的问题,尤其是与字符串结合后呈现出多姿多彩,在实际中使用也比较广泛,而且也是面试题中的常客,所以本节就结合几个典型的例子来体味下回文之趣。

解法一

同时从字符串头尾开始向中间扫描字串,如果所有字符都一样,那么这个字串就是一个回文。采用这种方法的话,我们只需要维护头部和尾部两个扫描指针即可。(java没有指针,因此维护两个变量一个初始值在开头一个在结尾

代码如下::

/*
     * 从两端向中间扫描
     */
    public static boolean isPrlindrome1(String s)
    {
        int i=0;
        int j=s.length()-1;
        while(i<=j)
        {
            if(s.charAt(i)!=s.charAt(j))
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

这是一个直白且效率不错的实现,时间复杂度:O(n),空间复杂度:O(1)。

解法二

上述解法一从两头向中间扫描,那么是否还有其它办法呢?我们可以先从中间开始、然后向两边扩展查看字符是否相等。参考代码如下:

/*
     * 从中间向两端扫描
     */
    public static boolean isPrlindrome2(String s)
    {
        int n=s.length();
        int j=0;
        int k=0;
        if(n%2==0)
        {
            j=n/2-1;
            k=n/2;
        }
        else 
        {
            j=n/2-1;
            k=n/2+1;
        }
        while(j>=0)
        {
            if(s.charAt(j)!=s.charAt(k))
            {
                return false;
            }
            j--;
            k++;
        }
        return true;
    }

重点是要找准中心点即可

时间复杂度:O(n),空间复杂度:O(1)。

虽然本解法二的时空复杂度和解法一是一样的,但很快我们会看到,在某些回文问题里面,这个方法有着自己的独到之处,可以方便的解决一类问题。(还没碰到过 不知道碰到了记不记得)