判断一个字符串是不是回文串如果不是判断他能不能通过交换字符变成回文串并输出交换次数
时间: 2024-10-24 18:13:43 浏览: 23
回文串(完美的代价)
4星 · 用户满意度95%
判断一个非回文串能否通过交换字符变成回文串,可以采用双指针法,一个从前往后,一个从后往前,记录下不匹配的字符及其位置。对于每对不匹配的字符,我们可以考虑交换它们,然后更新交换计数器。交换直到找到所有的回文对或指针相遇为止。
以下是简单的Java代码实现:
```java
public class Main {
public static void main(String[] args) {
String s = "abcba"; // 示例字符串,已经是一个回文串
if (!isPalindrome(s)) { // 如果不是回文
int exchanges = 0;
for (int i = 0, j = s.length() - 1; i < j; ) {
if (s.charAt(i) != s.charAt(j)) {
exchanges++; // 交换字符
char temp = s.charAt(i);
s = swapCharAt(s, i, j); // 交换i和j处的字符
i++;
j--;
} else {
i++;
j--;
}
}
System.out.println("可以通过交换字符变为回文,需要交换 " + exchanges + " 次");
} else {
System.out.println("已经是回文串,不需要交换");
}
}
public static String swapCharAt(String str, int i, int j) {
char[] chars = str.toCharArray();
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
public static boolean isPalindrome(String str) {
int start = 0;
int end = str.length() - 1;
while (start < end) {
if (str.charAt(start) != str.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
```
阅读全文