java中利用栈实现字符串回文算法

时间:2020-12-04 阿飞Sirx 人气:0

问题

给定一个由多个a和b组成的字符串数组，字符串中有一个特殊的字符X,位于字符串的正中间，例如（aaaabbbbXabaabbbb）,如何判定该字符串是否回文

简单算法

定义两个下标分别指向字符串的头和尾，每次比较两个下标位置的值是否相等，如果不相等，那么输入的
字符串不是回文，如果相等，左边的下表加1，右边的下表减1，重复上述步骤直至两个下标都指向字符串的正中间或者确定字符串不是回文

  /**
   * 判断字符串是否是回文
   */
  public int isPalindrome(String inputStr) {
    int i = 0;
    int j = inputStr.length();
    char[] chars = inputStr.toCharArray();
    while (i < j && chars[i] == chars[j]) {
      i++;
      j--;
    }
    if (i < j) {
      System.out.println("Not a Palindrome");
      return 0;
    } else {
      System.out.println("Palindrome");
      return 1;
    }
  }

利用栈判断是否回文

1.遍历字符数组，
2.在遍历过程中将经过的每个字符（X以前的字符）入栈
3.对于链表的后一半，把每个元素与栈顶元素比较，如果相等，执行一次出栈操作，并且移动到下一个元素继续比较
4.如果比较时出现不相等，那么输入的字符串不是回文
5.继续这个过程，直至栈空或者字符串不是回文

  /**
   * 利用栈判断字符回文
   */
  public boolean isPalindromeWithStack(String inputStr) {
    char[] inputChar = inputStr.toCharArray();
    LinkedListStack s = new LinkedListStack();
    int i = 0;
    while (inputChar[i] != 'X') {
      s.push(inputChar[i]);
      i++;
    }
    i++;
    while (i < inputChar.length) {
      if (s.isEmpty())
        return false;
      if (inputChar[i] != s.pop()) {
        return false;
      }
      i++;
    }
    //将来
    return true;
  }

Java判断是否为回文字符串

题目描述

输入一段字符串序列，字符串可能包括字母，数字，标点符号等类型字符，在判断该字符序列是否为回文时，只需判断字母和数字类型，其它类型自动忽略。
如：“A man, a plan, a canal: Panama” 是一段回文字符串
“race a car”则不是回文字符串

实现方法

从字符串的两端逐个进行比较，若遇到非字母或数字字符则将索引值加一或减一，如果两端字符不同，直接返回false，直到索引值在中间相遇也没有返回false则证明该字符串是回文字符串。

public static boolean isPalindrome(String str){
    if(str.equals(""))
      return true;
    str = str.toLowerCase();//将字符串的所有大写字母转小写
    int start = 0, end = str.length() - 1;

    //从字符两端分别逐个对比字符，不同则直接返回false
    while (start < end){
      //过滤掉非字母和数字字符
      while (!(str.charAt(start) >= 'a' && str.charAt(start) <= 'z' || str.charAt(start) >= '0' && str.charAt(start) <= '9'))
        start++;
      //过滤掉非字母和数字字符
      while (!(str.charAt(end) >= 'a' && str.charAt(end) <= 'z' || str.charAt(end) >= '0' && str.charAt(end) <= '9'))
        end--;
      //若字符不同，则直接返回false
      if(str.charAt(start) != str.charAt(end))
        return false;
      start++;
      end--;
    }
    return true;
  }

编程判断字符串是否为回文判断一个字符串是否是回文，例如单词‘level'

#include <stdio.h>
#include <string.h>

int main()
{
char a[100]= {0};
int i = 0;
int len = 0;
printf("please input character string:\n");
gets(a);
len = strlen(a); //计算输入字符串的长度；
for(i = 0; i < (len / 2); i++) //只需要判断前一半（len/2）长度就好了
{ 
if(a[i] != a[len - 1 - i]) //判断是否为回文数；
{
printf("不是回文数\n");
return 0;
}
}
printf("是回文数\n");
return 0;
}

加载全部内容