輸入一個字符串s敛劝,我們可以刪除字符串s中的任意字符,讓剩下的字符串形成一個對稱字符串纷宇,且該字符串為最長對稱字符串

輸入一個字符串s攘蔽,我們可以刪除字符串s中的任意字符,讓剩下的字符串形成一個對稱字符串呐粘,且該字符串為最長對稱字符串满俗。如:輸入google,則找到最長對稱字符串為goog作岖;如輸入abcda則能找到3個最長對稱字符串為aba/aca/ada唆垃。 若最長對稱字符串存在多個,則輸出多個相同長度的最長對稱字符串痘儡,且字符串中不包含特殊字符辕万。



import java.util.HashSet;
import java.util.Set;
import java.util.regex.Pattern;

/**
 * @author sunlichao on 2019-07-09.
 */
public class Test1 {

    /**
     * 根據(jù)特殊字符進行字符串分割
     * @param str 輸入字符串
     * @return
     */
    private static String[] stringFilter(String str) {
        String regEx = "[^a-zA-Z0-9]";
        Pattern p = Pattern.compile(regEx);
        return p.split(str);
    }

    /**
     * 遍歷生成的二維數(shù)組,遞歸查找最長路徑
     * @param a 第一個字符串
     * @param b 第二個字符串
     * @param mux 二維中間數(shù)組
     * @param i 二維數(shù)組raw位置
     * @param j 二維數(shù)組column位置
     * @param path 一次查找的字符串
     * @param paths 最終結(jié)果集合
     */
    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());
    }

    /**
     * 字符串s,我們可以刪除字符串s中的任意字符渐尿,讓剩下的字符串形成一個對稱字符串醉途,且該字符串為最長對稱字符串。
     * 原字符串反轉(zhuǎn)砖茸,成為查找最大公共子序列問題
     * @param input 待查找字符串
     * @return 查找結(jié)果
     */
    private static String findLCS(String input) {
        if (input == null || input.length() == 0) {
            return "";
        }

        // 將字符串反轉(zhuǎn)
        String reverse = new StringBuilder(input).reverse().toString();

        // 字符串長度
        int len = input.length();

        // 矩陣 -> 二維數(shù)組隘擎,第一行與第一列皆為零,兩個原因凉夯,一是方便算法越界處理货葬,二是在
        // 通過矩陣查找子串時,作為終止時間判斷使用劲够。
        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)) {
                    //取值為左上角值+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去重人柿。
        Set<String> paths = new HashSet<>();
        Test1.getAllLcs(input, reverse, tmp, input.length(), reverse.length(), "", paths);

        return String.join("/", paths);
    }

    /**
     * 包括對特殊字符柴墩,結(jié)果格式生成
     * @param input 待處理字符串
     * @return
     */
    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));
    }
}


參考:
https://segmentfault.com/q/1010000014740633?_ea=14643174
動態(tài)規(guī)劃 最長公共子序列(LCS) 過程圖解
https://blog.csdn.net/u012426298/article/details/82796660
https://blog.csdn.net/afei__/article/details/83153399

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末顷扩,一起剝皮案震驚了整個濱河市拐邪,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌隘截,老刑警劉巖扎阶,帶你破解...
    沈念sama閱讀 218,036評論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異婶芭,居然都是意外死亡东臀,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,046評論 3 395
  • 文/潘曉璐 我一進店門犀农,熙熙樓的掌柜王于貴愁眉苦臉地迎上來惰赋,“玉大人,你說我怎么就攤上這事呵哨×薇簦” “怎么了?”我有些...
    開封第一講書人閱讀 164,411評論 0 354
  • 文/不壞的土叔 我叫張陵孟害,是天一觀的道長拒炎。 經(jīng)常有香客問我,道長挨务,這世上最難降的妖魔是什么击你? 我笑而不...
    開封第一講書人閱讀 58,622評論 1 293
  • 正文 為了忘掉前任玉组,我火速辦了婚禮,結(jié)果婚禮上丁侄,老公的妹妹穿的比我還像新娘惯雳。我一直安慰自己,他們只是感情好鸿摇,可當我...
    茶點故事閱讀 67,661評論 6 392
  • 文/花漫 我一把揭開白布石景。 她就那樣靜靜地躺著,像睡著了一般户辱。 火紅的嫁衣襯著肌膚如雪鸵钝。 梳的紋絲不亂的頭發(fā)上糙臼,一...
    開封第一講書人閱讀 51,521評論 1 304
  • 那天庐镐,我揣著相機與錄音,去河邊找鬼变逃。 笑死必逆,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的揽乱。 我是一名探鬼主播名眉,決...
    沈念sama閱讀 40,288評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼凰棉!你這毒婦竟也來了损拢?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,200評論 0 276
  • 序言:老撾萬榮一對情侶失蹤撒犀,失蹤者是張志新(化名)和其女友劉穎福压,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體或舞,經(jīng)...
    沈念sama閱讀 45,644評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡荆姆,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,837評論 3 336
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了映凳。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片胆筒。...
    茶點故事閱讀 39,953評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖诈豌,靈堂內(nèi)的尸體忽然破棺而出仆救,到底是詐尸還是另有隱情,我是刑警寧澤矫渔,帶...
    沈念sama閱讀 35,673評論 5 346
  • 正文 年R本政府宣布彤蔽,位于F島的核電站,受9級特大地震影響蚌斩,放射性物質(zhì)發(fā)生泄漏铆惑。R本人自食惡果不足惜范嘱,卻給世界環(huán)境...
    茶點故事閱讀 41,281評論 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望员魏。 院中可真熱鬧丑蛤,春花似錦、人聲如沸撕阎。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,889評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽虏束。三九已至棉饶,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間镇匀,已是汗流浹背照藻。 一陣腳步聲響...
    開封第一講書人閱讀 33,011評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留汗侵,地道東北人幸缕。 一個月前我還...
    沈念sama閱讀 48,119評論 3 370
  • 正文 我出身青樓,卻偏偏與公主長得像晰韵,于是被迫代替她去往敵國和親发乔。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,901評論 2 355

推薦閱讀更多精彩內(nèi)容