首页 > 代码库 > Palindrome Partitioning

Palindrome Partitioning

2024-07-22 03:13:37   226人阅读

Given a string s, partitions such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning ofs.

For example, given s ="aab",
Return 

  [    ["aa","b"],    ["a","a","b"]  ]

这个题很明显需要DFS，然而实现时犯了一个很大错误。见AC代码。
public class Solution {    public List<List<String>> partition(String s) {    	List<List<String>> res = new ArrayList<>();    	List<String> list = new ArrayList<String>();    	dfs(s, list, res);    	return res;    }    public void dfs(String s,List<String> list,List<List<String>> res){    	if(s.length()<1){    		//巨大错误：！！！ 这里必须注意不能写成res.add(list); 因为后面list会改变，导致最终res里面为空    		res.add(new ArrayList<String>(list));    		return;    	}    	for(int i=0;i<s.length();i++){    		if(IsPalindrome(0, i, s)){    			list.add(s.substring(0,i+1));    			dfs(s.substring(i+1), list, res);    			list.remove(list.size()-1);    		}    	}    }    boolean IsPalindrome(int start ,int end,String s){    	while(start<end){    		if(s.charAt(start)==s.charAt(end)){    			start++;    			end--;    		}else {				return false;			}    	}    	return true;    }}

也可以换种写法思路一样实现有点细微差别：上面是每次改变字符串递归，下面写法是通过下标改变实现字符串变动。
public List<List<String>> partition(String s) {        		List<String> item = new ArrayList<String>();        List<List<String>> res = new ArrayList<>();                if(s==null||s.length()==0)            return res;              dfs(s,0,item,res);        return res;    }        public void dfs(String s, int start, List<String> item, List<List<String>> res){        if (start == s.length()){            res.add(new ArrayList<String>(item));            return;        }              for (int i = start; i < s.length(); i++) {            String str = s.substring(start, i+1);            if (isPalindrome(str)) {                item.add(str);                dfs(s, i+1, item, res);                item.remove(item.size() - 1);            }        }    }      public boolean isPalindrome(String s){         int low = 0;         int high = s.length()-1;         while(low < high){             if(s.charAt(low) != s.charAt(high))                return false;             low++;             high--;         }         return true;    }}

Palindrome Partitioning


联系
我们