Java怎么解決分割回文串問題

本篇內容主要講解“Java怎么解決分割回文串問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java怎么解決分割回文串問題”吧!

題目

給出一個字符串s，分割s使得分割出的每一個子串都是回文串

計算將字符串s分割成回文分割結果的最小切割數

例如: 給定字符串s=“aab”,

返回1，因為回文分割結果[“aa”,“b”]是切割一次生成的。

思路分析

首先，已知字符串s的長度為len，想要求前len個字符串被切割成回文串所需要的最小切割數，就會很自然的想到求前i個字符形成的字符串切割成回文串需要的最小切割數，即為狀態F（i）。

然后，會想到前i個字符形成的字符串分割變成回文串需要的最大切割數為i-1。例如字符串"aab"，切2刀形成長度為1的回文串"a"，“a”，“b”。

再然后，關鍵在于求解最小切割數的過程，這里采取暴力求解，定義變量j,使之小于i，在我們已知狀態F（j）的情況下（即前j個字符形成的字符串的最小切割次數），如果[j+1，i]是回文串，那么再來上一刀就可以求出當前用最少的切割次數。那么此時F（i）= min（F（i），F（j）+1），意思就是在上一次求得的前i個字符串的分割次數和這一次求得的次數進行對比，取最小值。（注：這里的[j+1,i]指的是字符串第j+1個字符到第i個字符的意思，并非字符串下標索引，寫代碼時，轉換成索引就應該是求下標為j-1的字符到下標為i的字符形成的字符串是否為回文串）

緊接著，就該實現判斷是否為回文串的方法，簡單的思想就是，為該方法提供字符串s，提供子串的起始下標start與終點下標end，start<end的條件下，使start向后走，end向前走，但凡對應到字符串s中的字符不一樣，就說明不是回文串，返回false，如果成功遍歷完了循環，說明是回文串，返回true。

最后，將F（len）的值返回。

動歸四角度：

1.狀態定義F（i）：字符串s的前i個字符的最小分割次數；

2.狀態間的轉移方程定義：F（i）=min（F（i），F（j）+1），0 <= j < i,且F（j）為已知狀態，當[j+1,i]為回文串時，執行此狀態轉移方程

3.狀態的初始化：F（i） = i-1，注意F（0）為-1；

例如，當字符串為"aa"，因為[1,2]為回文串，F（2）= min（F（2），F（0）+1）=min（1，0）= 0，得到正確答案

4.返回結果 ：F（s.length())；

案例說明

為了方便理解，這里采取了更長的字符串"aabaa",一步步帶你走過程。

初級代碼

import java.util.*;
public class Solution {
    //判斷是否為回文串
    public boolean func(String s,int start,int end) {
        while(start<end) {
            if(s.charAt(start)!=s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int minCut (String s) {
        int len = s.length();//字符串的長度
        if(len == 0) return 0;//當長度為0時直接返回0
        int[] count = new int[len + 1];//用于記錄狀態
        //狀態初始化
        for(int i = 0;i <= len;i ++) {
            count[i] = i-1;
        }
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= i-1;j++) {
                if(func(s,j,i-1)) {
                    count[i] = Math.min(count[i],count[j]+1);//狀態轉移方程
                }
            }
        }
        return count[len];//返回結果
    }
}

在整個進行狀態計算的過程中，兩層for循環時間復雜度為O（N2）,判斷是否為回文串的方法時間復雜度為O（N），因此總的來說，總的時間復雜度為O（N3）

代碼升級

可以看出來，用上面的代碼時間復雜度還是比較高的，因此代碼還需升級才是

1.回文串動歸

首先，關于回文串的判斷方法，每次判斷是否要進行狀態轉移方程時都要調用回文串方法，這真的有必要嗎，或許也可以使用動態規劃的思想將每種字符子串是否為回文串的狀態記錄下來。

狀態四角度：

1.狀態定義F（i，j）：字符區間[i,j]是否為回文串

2.狀態間的轉移方程定義F（i，j）：

如果i == j，表示單字符，F（i，j） = true；

如果j == i+1，表明倆字符是緊挨著的，如果在總字符串s中對應的字符相同，F（i，j）= true，反之F（i，j） = false；

其他的情況中，F（i，j） = (s.charAt(i) == s.charAt(j)) && F（i+1，j-1）；

該轉移方程的意思為字符首尾字符相同，且去掉字符區間的首位字符后的字符區間的狀態F（i+1，j-1）仍然為回文串才證明[i,j]字符串區間為回文串即F（i，j）= true

3.狀態的初始化：F（i，j） = false

4.返回結果狀態二維布爾類型數組

注：由于在狀態轉移的過程中，求F（i，j）會只用到之前已經計算過的狀態F（i+1，j-1），這就意味著i需要從后向前遍歷，使用的是已經更新過結果的值

import java.util.*;
public class Solution {
    //判斷是否為回文串
    public boolean[][] func2 (String s) {
        int len = s.length();//字符串的長度
        boolean[][] ret = new boolean[len][len];
        //記錄狀態的二維數組，默認值為false
        //由于i<=j<len,所以ret數組實際只更新了一半
        for(int i = len;i >= 0;i--) {
            for(int j = i;j<len;j++) {
                if(i == j) {
                    ret[i][j] = true; //單字符比為回文串
                }else if(j == i+1) {
                    if(s.charAt(i) == s.charAt(j)) {
                        ret[i][j] = true; //相鄰字符相同為回文串
                    }else{
                        ret[i][j] = false;//相鄰字符不同就不是回文串
                    }
                }else{
                    ret[i][j] = (s.charAt(i) == s.charAt(j)) && ret[i+1][j-1];
                    //其余轉移情況
                }
            }
        }
        return ret;//返回結果
    }
    public int minCut (String s) {
        int len = s.length();
        if(len == 0) return 0;
        int[] count = new int[len + 1];
        //狀態初始化
        for(int i = 0;i <= len;i ++) {
            count[i] = i-1;
        }
        boolean[][] ret = func2(s);//調用判斷回文串方法，獲得所有字符子串的是否為回文串的情況
        for(int i = 1;i <= len;i++) {
            for(int j = 0;j <= i-1;j++) {
                //直接在ret數組中找結果，避免反復調用回文串判斷方法
                if(ret[j][i-1]) {
                    count[i] = Math.min(count[i],count[j]+1);//狀態轉移方程
                }
            }
        }
        return count[len];//返回結果
    }
}

在該方法中，判斷回文串的方法時間復雜度為O（N2），但因為在主方法中只調用了一次，且回文串判斷方法中只更新了一般的值，因此總的時間復雜度為O（N2）~O(2*N2)

2.綜合動歸

可以看的出來上面的代碼還是比較長的，回文串判斷方法用到了兩層循環，主方法也用到了兩層循環，這不也是優化的方向蠻，或許可以把它們放在同一個兩層循環中。

注：由于回文串判斷方法中的i是一定要從后向前遍歷的，因此主函數的初識值就需要調整為count[i] = len - i - 1，返回的結果為F（0）

import java.util.*;
public class Solution {
    public int minCut(String s) {
        int len = s.length();//字符串的長度
        if(len == 0) return 0;
        int []count = new int[len+1]; //存放最小分割次數狀態的數組
        boolean [][]p = new boolean[len][len];//存放[i,j]字符區間是否為回文串的二維數組
        for(int i = 0; i <= len; i++) count[i] = len - i - 1;//狀態初始化
        for(int i = len-1;i >= 0;i--){
            for(int j = i;j < len;j++){
                //j-i<2 條件成立且第一個條件成立包含著單個字符串和相鄰字符串的情況
                //p[i+1][j-1] 為 ture 且第一個條件成立則代表著其他的回文串狀態轉移類型
                //以上情況有一項成立則F（i，j）為 ture
                if(s.charAt(i) == s.charAt(j) && (j-i<2||p[i+1][j-1])){
                    p[i][j] = true;
                    count[i] = Math.min(count[i],count[j+1]+1);//狀態轉移方程
                }
            }
        }
        return count[0];//返回結果
    }
}

通過這樣的方法，直接將時間復雜度降到了O（N2）

3.奇思妙想

上面幾種方法，需要將回文串的判斷狀態都記錄下來，且判斷回文串的方法都是從子字符串的兩頭向中間進行判斷，或許有一種方法，可以直接不用記錄下來每種子字符串的是否為回文串的狀態，并且從中間向兩頭進行判斷回文串。

可以設置兩個變量i和j，[i,j]且j==i代表著下標為i的單個字符，必定是回文串，F（j+1）= min（F（j+1），F（i）+1），以此為中心，i--,j++,如果區間兩頭的字符相同，說明[i-1,j+1]的區間字符串為回文串，在不超出原字符串s的總區間[0,len-1]的循環情況下，重復上面的操作，直到循環條件不成立

回文串可能是奇數個字符，也可能是偶數個字符，上面的情況是奇數個字符的情況，換成偶數個字符的情況只需要判斷[i,i+1]是否為回文串，如果是，就參考上面的方式，以此為中心向兩頭展開，求以[i,i+1]為中心最長的回文串,從而求出每個狀態的最小分割數。

案例說明：

import java.util.*;
public class Solution {
    public int minCut(String s) {
        int len = s.length();//字符串的長度
        if(len == 0) return 0;
        int[] count = new int[len + 1];
        for(int i = 0; i <= len; i++) count[i] = i - 1;//狀態初始化
        for(int i = 0; i < len; i++) {
            func3(s, i, i, count);//奇數個字符的回文串
            func3(s, i, i + 1, count);//偶數個字符的回文串
        }
        return count[len];//返回結果
    }     
    private  void func3(String s, int i, int j, int[] count) {
        //不超過字符串s的區間范圍且下標i的字符和下標j的字符相等的條件下向兩頭擴展，得到最長的回文串，以此來求出狀態
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            count[j + 1] = Math.min(count[j + 1], count[i] + 1); //狀態轉移
            --i;//左區間擴展一格
            ++j;//右區間擴展一格
        }
        return;
    }  
}

到此，相信大家對“Java怎么解決分割回文串問題”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！