Palindrome Partitioning

Java

public class Solution {
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
		public List<List<String>> partition(String s) {
			List<List<String>> res = new ArrayList<>();
			dfs(s, 0, new ArrayList<String>(), res);
			return res;
		}
		private void dfs(String str, int index, List<String> path, List<List<String>> res) {
			if (index == str.length()) {
				res.add(new ArrayList<>(path));
			}
			
			for (int i = index; i < str.length(); i++) {
				String subStr = str.substring(index, i + 1); //左闭右开区间
				if (isPalindrome(subStr)) {
					path.add(subStr);
					dfs(str, i + 1, path, res);
					path.remove(path.size() - 1);
				}
			}
			
		}
		private boolean isPalindrome(String str) {
				int i = 0;
				int j = str.length() - 1;
				while (i < j) {
						if (str.charAt(i) != str.charAt(j)) return false;
						i++;
						j--;
				}
				return true;
		}
}