131. Palindrome Partitioning - Medium

前往題目

想法

• backtracking把所有組合都看過，每次要判斷是否是palindrome然後才加入

思路

1. 平常的backtrack
2. 要紀錄起始點，然後每個循環都要判斷是否為palindrome

Code

class Solution {
    List<List<String>> res = new LinkedList<>();
    LinkedList<String> track = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtrack(s, 0);
        return res;
    }

    private void backtrack(String s, int start) {
        // Base case
        if (start == s.length()) {
            res.add(new ArrayList<String>(track));
            return; // 這裡return與否都行,因為下面的循環也開始不了
        }

        // 用start當作開頭才能避免遞迴時又從開頭開始取
        for (int i = start; i < s.length(); ++i) {
            // 判斷當前substring是否是回文
            if (!isPalin(s, start, i)) {
                continue;
            }
            // 加入當前的substring
            track.addLast(s.substring(start, i + 1));
            // 從i + 1當作起點
            backtrack(s, i + 1);
            track.removeLast();
        }
    }

    private boolean isPalin(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) {
                return false;
            }
            ++l;
            --r;
        }
        return true;
    }
}