leetcode

0 // Backtracking

1 class Solution {

2 vector<string> st;

3 vector<vector<string>> res;

4

5 bool valid(const string &s) {

6 int i = 0, j = s.size() - 1;

7 while (i < j)

8 if (s[i++] != s[j--]) return false;

9 return true;

10 }

11

12 void dfs(const string &s, int pos) {

13 if (pos == s.size()) res.push_back(st);

14

15 string crnt = "";

16 for (int i = pos; i < s.size(); i++) {

17 crnt += s[i];

18 if (valid(crnt)) {

19 st.push_back(crnt);

20 dfs(s, i + 1);

21 st.pop_back();

22 }

23 }

24 }

25

26 public:

27 vector<vector<string>> partition(string s) {

28 dfs(s, 0);

29 return res;

30 }

31 };

32

33 // Backtracking with DP

34 class Solution {

35 vector<string> st;

36 vector<vector<string>> res;

37

38 void dfs(const string &s, int pos, vector<vector<bool>> &dp) {

39 if (pos == s.size()) res.push_back(st);

40

41 string crnt = "";

42 for (int i = pos; i < s.size(); i++) {

43 crnt += s[i];

44 if (s[pos] == s[i] && (i - pos < 2 || dp[pos + 1][i - 1])) {

45 dp[pos][i] = true;

46 st.push_back(crnt);

47 dfs(s, i + 1, dp);

48 st.pop_back();

49 }

50 }

51 }

52

53 public:

54 vector<vector<string>> partition(string s) {

55 vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));

56 dfs(s, 0, dp);

57 return res;

58 }

59 };