回文字符串算法多种实现

前言

回文字符串,是指正读和倒读的结果一样的字符串,从结构上来看,两侧的字符呈中心对称。在汉语中,有很多有趣的回文诗词,回文对联熟语,比如“响水池中池水响,黄金谷里谷金黄”、“雾锁山头山锁雾,天连水尾水连天”等。

算法语言

  • Python
  • C#

详情

数字121从左往右读与从右往左读是一样的,这种数称为回文数。
找出>=0并且<=n的全部回文数。

注意:单个的数字0,数字1,... 数字9也认为是回文数。

输入格式:

n

输出格式:

多行输出,一行一个数

输入样例:

13

输出样例:

0
1
2
3
4
5
6
7
8
9
11

 算法实现

使用for循环以及切片方法实现

//使用语言Python
intNum = int(input())
for i in range(intNum+1):
   if i<10:
    print(i)
   elif i<100:
    gw=i%10
    bw=int(i/10)
    if  gw==bw:
        print(i)
   else:
    intStr=str(i)
    intcount=len(intStr)
    halfindex=(int)(intcount/2)
    intisDouble=intcount%2==0
    left=intStr[0:(intisDouble and  halfindex-1 or halfindex) ]
    right=intStr[(intisDouble and  halfindex or halfindex)+1::intcount]
    if left==right:
        if  intisDouble:
            if intStr[halfindex-1]==intStr[halfindex]:
                print(i)
        else:
            print(i) 
         

笔者这里主要为了实现研究回文算法,实际上可以从Python库中调用回文字符串判断的函数。

让我们单独把判断回文字符串的算法拿出来分析

使用For循环实现

只要从前往后判断中心点(根据Length奇偶,中心点存在一个或两个)两边的字符串是否相等,遍历过程应保证两边的字符都相等,否则不是回文字符串。当遍历到中心点或index相同时候则退出循环(如果i>=j发生则说明当前已经遍历到了中心点),则该字符串为回文字符串。

        static void Main(string[] args)
        {
            Console.WriteLine("请输入一组数字");
            string str = Console.ReadLine();
            Console.WriteLine($"字符串{str}是回文:{IsPalindromic_For(str)}");
            Console.ReadLine();
            
        }
        public static bool IsPalindromic_For(string str)
        {
            int i = 0;
            int j = str.Length-1;
            while (i<j)
            {
                if (str[i]!=str[j])
                {
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }

 

使用堆栈实现

我们可以利用栈先进后出的特性,把字符串存入栈中,再遍历时候再从栈中一一取出,得到一个逆序的字符串。拿到逆序的字符串与原字符串进行比较,判断字符串是否相等即可。

//C#语言实现        
static void Main(string[] args)
        {
            Console.WriteLine("请输入一组数字");
            string str = Console.ReadLine();
            Console.WriteLine($"字符串{str}是回文:{IsPalindromic(str)}");
            Console.ReadLine();
            
        }
        public static bool IsPalindromic(string str)
        {
            //利用堆栈的特性
            Stack<char> stack = new Stack<char>();
            //Queue<char> queue = new Queue<char>();
            //分别放入
            foreach (char c in str)
            {
                stack.Push(c);
                //queue.Enqueue(c);
            }
            //string front = null;
            string last = "";
//可以优化,只需要对一半字符串进行判断即可,没必要遍历所有字符串。
            while (stack.Count>0)
            {
                //front+=queue.Dequeue();
                char c=stack.Pop();
                if (str[last.Length] !=c)
                {
                    return false;
                }
                last += c;
            }
            return true;
        }

上面的算法,其实可以认为将原字符串逆序了,使用逆序函数也可以。最终问题是比较逆序前后的字符串。

优化:实际上,上面算法有一定的缺陷的,是可以优化的,我们知道算法在计算机中运行需要耗费一定的时间,我们应当尽量降低不必要的执行次数,以降低时间复杂度。在这里我们只需要对一半字符串进行判断即可,没必要遍历所有字符串。

 

 

 

作者:Miracle
来源:麦瑞克博客
链接:https://www.unitymake.com/archives/programming-life/datastruct/2013
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0许可协议,转载请注明!
THE END
分享
打赏
海报
回文字符串算法多种实现
前言 回文字符串,是指正读和倒读的结果一样的字符串,从结构上来看,两侧的字符呈中心对称。在汉语中,有很多有趣的回文诗词,回文对联熟语,比如“响水池中池……
<<上一篇
下一篇>>
文章目录
关闭
目 录