输入一个字符串 str，可以删除字符串 str 中的任意字符，让剩下的字符串形成一个对称字符串，且该字符串为最长对称字符串

Z时代
2024-01-10
分类：IT

题目:

输入一个字符串s，我们可以删除字符串s中的任意字符，让剩下的字符串形成一个对称字符串，且该字符串为最长对称字符串。

例如:

输入google，则找到最长对称字符串为goog

输入abcda则能找到最长对称字符串为aba。

最长对称字符串存在多个，则输出多个相同长度的最长对称字符串。

输入输出示例:

public static void main(String[] args){
    // TODO: 输出最长对称字符串: goog
    String input1 = "google";
    // TODO: 输出最长对称字符串: aca
    String input2 = "abcda";
    // TODO: 输出最长对称字符串: opo/upu
    String input3 = "opo-upu";}

回答：

问题已经解决

由于提供的代码对于opo-upu这样的测试用例无法得到正确的结果，所以，参考了 @studio 和 Java——最长公共子串问题LCS提供的思路之后，编写了如下代码：
图片描述

findLCS(String input): String 获取最大回文串

private static String findLCS(String input) {
    // 要返回的结果
    StringBuilder result = new StringBuilder();
    // 将字符串反转
    String reverse = new StringBuilder(input).reverse().toString();
    // 字符串长度
    int len = input.length();
    // 矩阵 -> 二维数组
    int[][] temp = new int[len][len];
    // 横向字符
    char[] hor = input.toCharArray();
    // 纵向字符
    char[] ver = reverse.toCharArray();
    // 给矩阵(二维数组赋值)
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            temp[i][j] = (hor[j] == ver[i]) ? 1 : 0;
        }
    }
    // 找到第一个横向
    int horIndex = -1;
    for (int i = 0; i < len - 1; i++) {
        if (temp[0][i] == 1) {
            horIndex = i;
        }
    }
    // 找到第一个纵向
    int verIndex = -1;
    for (int i = 0; i < len - 1; i++) {
        if (temp[i][0] == 1) {
            verIndex = i;
        }
    }
    // 处理特殊情况的标识，如 abcda
    boolean flag = false;
    int indexHor = 0;
    if (horIndex != -1 && horIndex != 0) {
        for (int i = horIndex; i < len; i++) {
            if (temp[indexHor++][i] == 1) {
                result.append(hor[i]);
            }
        }
        flag = true;
    }
    int indexVer = verIndex;
    if (verIndex != -1) {
        if (flag) {
            result.append("/");
        }
        for (int i = 0; i < len - verIndex; i++) {
            if (temp[indexVer++][i] == 1) {
                result.append(hor[i]);
            }
        }
    }
    return result.toString();}

main(String[] args): void 主方法

public static void main(String[] args) {
    String input1 = "google";
    String input2 = "abcda";
    String input3 = "opo-upu";
    System.out.println(input1 + " -> " + findLCS(input1)); // 结果: google -> goog
    System.out.println(input2 + " -> " + findLCS(input2)); // 结果: abcda -> aca
    System.out.println(input3 + " -> " + findLCS(input3)); // 结果: opo-upu -> opo/upu}

回答：

https://www.cnblogs.com/yingp...
这个有个JAVA代码，你可以参考下。我一开始是用C写的，感觉太麻烦了，JAVA不太会，但是看懂了一点，希望可以帮到你

回答：

package sun.interview;
import java.util.HashSet;
import java.util.Set;
import java.util.regex.Pattern;
/**
 * @author sunlichao on 2019-07-09.
 */
public class Test1 {
    public static String[] stringFilter(String str) {
        String regEx = "[^a-zA-Z0-9]";
        Pattern p = Pattern.compile(regEx);
        return p.split(str);
    }
    private static void getAllLcs( String a, String b, int[][] mux, int i, int j, String path, Set<String> paths) {
        StringBuilder pathBuilder = new StringBuilder(path);
        while (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                pathBuilder.append(a.charAt(i - 1));
                --i;
                --j;
            }else {
                if (mux[i - 1][j] > mux[i][j - 1]) {
                    --i;
                } else if (mux[i - 1][j] < mux[i][j - 1]) {
                    --j;
                } else {
                    getAllLcs(a, b, mux, i - 1, j, pathBuilder.toString(), paths);
                    getAllLcs(a, b, mux, i, j - 1, pathBuilder.toString(), paths);
                    return;
                }
            }
        }
        paths.add(pathBuilder.toString());
    }
    public static String findLCS(String input) {
        if (input == null || input.length() == 0) {
            return "";
        }
        // 要返回的结果
        StringBuilder result = new StringBuilder();
        // 将字符串反转
        String reverse = new StringBuilder(input).reverse().toString();
        // 字符串长度
        int len = input.length();
        // 矩阵 -> 二维数组
        int[][] tmp = new int[len + 1][len + 1];
        for (int i = 1; i < len + 1; i++) {
            for (int j = 1; j < len + 1; j++) {
                if (input.charAt(i - 1) == reverse.charAt(j - 1)) {
                    tmp[i][j] = tmp[i - 1][j - 1] + 1;
                } else {
                    tmp[i][j] = Math.max(tmp[i - 1][j], tmp[i][j - 1]);
                }
            }
        }
        Set<String> paths = new HashSet<>(){};
        Test1.getAllLcs(input, reverse, tmp, input.length(), reverse.length(), "", paths);
        return String.join("/", paths);
    }
    public static String maxs(String input) {
        String[] prepare = stringFilter(input);
        StringBuffer sb = new StringBuffer();
        for (String str : prepare) {
            String result = findLCS(str);
            sb.append(result);
            sb.append("/");
        }
        return sb.substring(0, sb.length()-1);
    }
    public static void main(String[] args) {
        // TODO 输出最长对称字符串：goog
        String input1 = "google";
        System.out.println(maxs(input1));
        // TODO 输出3个最长对称字符串：aba/aca/ada
        String input2 = "abcda";
        System.out.println(maxs(input2));
        // TODO 输出2个最长对称字符串：pop/upu，不会输出特殊字符的对称字符串p-p
        String input3 = "pop-upu";
        System.out.println(maxs(input3));
    }}