leetcode131：分割回文串

题目链接

leetcode

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。
返回 s 所有可能的分割方案。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

/*
    回溯 + 记忆化搜索

    枚举所有方案。对字符串从前往后搜索，搜索时维护如下几个状态：
    1.已经划分好的区间列表
    2.当前在枚举的区间
    3.枚举字符串 s 的下标
    4.字符串 s

    时间复杂度：O(2^n*n)
        最多有多少个合法方案？
        在相邻字符之间放板子，每种放板子的方法对应一种划分方案，
        每个字符间隔有放和不放两种选择，所以总共有 2^(n−1) 个方案。
        对于每个方案，需要 O(n) 的时间来记录方案。
        所以，总时间复杂度是 O(2^n*n)。
    空间复杂度：O(n^2)
        这里不计算返回答案占用的空间。
        数组 f 需要使用的空间为 O(n^2) 
        在回溯的过程中，使用的栈空间 O(n) ，存储当前字符串分割方法的空间 O(n)。
*/
class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // f = vector<vector<bool>> (n, vector<bool>(n, true));
        f = vector<vector<bool>> (n, vector<bool>(n, true));
        for (int i = n - 1; i >= 0; i --) {
            for (int j = i + 1; j < n; j ++) {
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }
        dfs(s, 0);

        return res;
    }

    void dfs(string& s, int i) {
        if (i == s.size()) {
            res.push_back(path);
            return;
        }

        for (int j = i; j < s.size(); j ++) {
            if (f[i][j]) {
                path.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                path.pop_back();
            }
        }
    }

private:
    vector<vector<string>> res;
    vector<vector<bool>> f;
    vector<string> path; 
};

/*
    思路同上，回溯 + 记忆化搜索
*/
class Solution_1 {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        // f = vector<vector<int>> (n, vector<bool>(n, true));
        f.assign(n, vector<int>(n));
        dfs(s, 0);

        return res;
    }

    void dfs(string& s, int i) {
        if (i == s.size()) {
            res.push_back(path);
            return;
        }

        for (int j = i; j < s.size(); j ++) {
            if (isPalindrome(s, i, j) == 1) {
                path.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                path.pop_back();
            }
        }
    }

    // 记忆化搜索，f[i][j]（0 表示未搜索，1 表示是回文串，-1 表示不是回文串）
    int isPalindrome(const string& s, int i, int j) {
        if (f[i][j]) return f[i][j];
        if (i >= j) return f[i][j] = 1;
        return f[i][j] = (s[i] == s[j] ? isPalindrome(s, i + 1, j - 1) : -1);
    }

private:
    vector<vector<string>> res;
    vector<vector<int>> f;
    vector<string> path; 
};

int main() {
    Solution solution;
    string s = "aab";
    vector<vector<string>> partitions = solution.partition(s);
    cout << "Partitions of the string 'aab' are:" << endl;
    for (const vector<string>& partition : partitions) {
        for (const string& palindrome : partition) {
            cout << palindrome << " ";
        }
        cout << endl;
    }

    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"reflect"
)

/*
   回溯算法：
       使用回溯算法生成所有可能的分割方式。
       回溯算法通过递归模拟所有可能的分割路径，每次选择一个分割点，并在递归返回时恢复状态。
   回文检查：
       使用辅助函数 isPalindrome 检查一个子串是否是回文。
   结束条件：
       如果已经处理到字符串的末尾，将当前路径加入结果列表。

    时间复杂度：O(n*2^n)
        在最坏情况下，每个字符都可能是一个分割点，时间复杂度为 O(2^n)，其中 n 是字符串的长度。
        每次检查一个子串是否是回文的时间复杂度为 O(n)。
        因此，总时间复杂度为 O(n*2^n)。
    空间复杂度：
        递归调用栈的深度为 O(n)。
        当前路径 path 的空间复杂度为 O(n)。
        结果列表 result 的空间复杂度为 O(2^n)。
        因此，总空间复杂度为 O(n*2^n)。
*/
// partition 将字符串分割成多个回文子串
func partition(s string) [][]string {
	var result [][]string
	var backtrack func(path []string, start int)

	backtrack = func(path []string, start int) {
		// if start == len(s) {
		// 	// 如果已经处理到字符串的末尾，将当前路径加入结果
		// 	temp := make([]string, len(path))
		// 	copy(temp, path)
		// 	result = append(result, temp)
		// 	return
		// }
        if start == len(s) {
            // 如果已经处理到字符串的末尾，将当前路径加入结果
            result = append(result, append([]string(nil), path...))
            return
        }

		// 尝试从 start 开始的所有可能分割
		for end := start + 1; end <= len(s); end ++ {
			substr := s[start:end]
			if isPalindrome(substr) {
				// 如果当前子串是回文，加入路径并递归处理
				backtrack(append(path, substr), end)
			}
		}
	}

	// 开始回溯
	backtrack([]string{}, 0)
	return result
}

// isPalindrome 判断一个字符串是否是回文
func isPalindrome(s string) bool {
	for i := 0; i < len(s) / 2; i ++ {
		if s[i] != s[len(s) - 1 - i] {
			return false
		}
	}
	return true
}

func main() {
	// 测试用例
	testCases := []struct {
		s        string
		expected [][]string
	}{
		{
			s: "aab",
			expected: [][]string{
				{"a", "a", "b"},
				{"aa", "b"},
			},
		},
		{
			s: "a",
			expected: [][]string{
				{"a"},
			},
		},
	}

	for i, tc := range testCases {
		fmt.Printf("Test Case %d, Input: s = %s\n", i+1, tc.s)
		result := partition(tc.s)

		// if fmt.Sprint(result) == fmt.Sprint(tc.expected) {
        if reflect.DeepEqual(result, tc.expected) {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}