首页 > 代码库 > 回文字符串问题
回文字符串问题
一、判断一个字符串是否为回文字符串（aba）
public static boolean is_hwzfs(String s, int i, int j) { if (i > j) return false; for (int k = i; k <= j; ++k) { if (s.charAt(k) != s.charAt(j + i - k)) { return false; } } return true; }
二、求一个字符串的最长回文字符串长度并输出
1）暴力枚举
1 public static boolean is_hwzfs(char[] s, int i, int j) { 2 if (i > j) return false; 3 for (int k = i; k <= j; ++k) { 4 if (s[k] != s[j + i - k]) { 5 return false; 6 } 7 } 8 return true; 9 }10 11 public static void main(String[] args) {12 13 Scanner cin = new Scanner(System.in);14 String s = cin.nextLine();15 16 int len = s.length();17 int max = 1;18 int x = 0, y = 0;19 int[] p = new int[len];20 char[] ans = new char[len];21 int index = -1;22 for (int i = 0; i < len; ++i) {23 char ch = s.charAt(i);24 if (Character.isLetter(ch)) {25 p[++index] = i;26 ans[index] = Character.toLowerCase(ch);27 }28 }29 30 31 for (int i = 0; i <= index; ++i) {32 for (int j = i; j <= index; ++j) {33 if (is_hwzfs(ans, i, j)) {34 if (max < (j - i + 1)) {35 max = j - i + 1;36 x = p[i];37 y = p[j];38 }39 }40 }41 }42 System.out.println("max= " + max);43 for (int i = x; i <= y; ++i) {44 System.out.print(s.charAt(i));45 }46 System.out.println();47 }
2）确定字符串中心，向两边扩展枚举
- 长度为奇数: 判断 s[i-j]与s[i+j] (2*j+1)
- 长度为偶数：判断 s[i-j]与 s[i+j+1] (2*(j+1))
注意 i为字符串中心，j为向两边扩展的长度
法一：
法二：
public static void main(String[] args) { Scanner cin = new Scanner(System.in); String s = cin.nextLine(); int len = s.length(); int max = 1; int x = 0, y = 0; int[] p = new int[len]; char[] ans = new char[len]; int index = -1; for (int i = 0; i < len; ++i) { char ch = s.charAt(i); if (Character.isLetter(ch)) { p[++index] = i; ans[index] = Character.toLowerCase(ch); } } for (int i = 0; i <= index; ++i) { for (int j = 0; (i - j > 0) && (i + j <= index); ++j) { if (ans[i - j] != ans[i + j]) break; if ((2 * j + 1) > max) { x = p[i - j]; y = p[i + j]; max = 2 * j + 1; } } for (int j = 0; (i - j > 0) && (i + j + 1 <= index); ++j) { if (ans[i - j] != ans[i + j + 1]) break; if (2 * (j + 1) > max) { x = p[i - j]; y = p[i + j + 1]; max = 2 * (j + 1); } } } System.out.println("max= "+max); for (int i = x; i <= y; ++i) { System.out.print(s.charAt(i)); } System.out.println(); }
回文字符串问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。