LeetCode-Palindrome Partitioning

浅浅的花香味﹌ 2022-08-06 18:58 122阅读 0赞

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

Return all possible palindrome partitioning of s.

For example, given s = `"aab"`,  
Return

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

很显然题目要用回溯法，回溯法入门可以看之前的博客，自己的解法方案如下：

public class PalindromePartitioning {
    	boolean flag = true;
    	boolean[] visit;
    	Map<String, Boolean> map = new HashMap<>(); 
        public List<List<String>> partition(String s) {
        	visit = new boolean[s.length()];
        	List<List<String>> lists = new ArrayList<>();
        	if (s != null && !s.isEmpty())
        		partitionString(lists, s, 1);
            return lists;
        }
        public void partitionString(List<List<String>> lists, String s, int depth) {
        	if (depth == s.length()) {
        		List<String> list = new ArrayList<>();
        		int pre = 0, i = 0;
        		for (; i < s.length(); i++) {
        			if (visit[i]) {
        				String sub = s.substring(pre, i);
        				if (!isPal(sub)) {
        					return;
        				}
        				list.add(sub);
        				pre = i;
        			}
        		}
    			if (pre == 0) {
    				if (!isPal(s)) {
    					return;
    				}
    				list.add(s);
        		} else {
        			String sub = s.substring(pre, i);
        			if (!isPal(sub)) {
        				return;
        			}
        			list.add(sub);
        		}
        		lists.add(list);
        		return;
        	} 
       		visit[depth] = true;
       		if (pruning(s, depth)) {
       			partitionString(lists, s, depth+1);
       		}
       		visit[depth] = false;
       		partitionString(lists, s, depth+1);
        }
        public boolean pruning(String s, int depth) {
        	int i = depth-1;
        	while (i > 0) {
        		if (visit[i] == true) {
        			break;
        		}
        		i--;
        	}
        	String sub = s.substring(i, depth);
        	return isPal(sub);
        }
        public boolean isPal(String sub) {
        	if (map.get(sub) == null || map.get(sub) == false) {
    			boolean isPal = isPalindrome(sub);
    			map.put(sub, isPal);
    			if (!isPal) {
    				return false;
    			}
    		}
        	return true;
        }
    	public boolean isPalindrome(String s) {
        	if (s == null || s.isEmpty()) {
        		return false;
        	}
            int i = 0, j = s.length()-1;
            while (i < j) {
            	if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
            		return false;
            }
            return true;
        }
    	public static void main(String[] args) {
    		String s = "efeef";
    		PalindromePartitioning pp = new PalindromePartitioning();
    		System.out.println(pp.partition(s));
    	}
    }

首先本题跟之前求解一个集合的子集很像，或者说回溯的题都很像。在实现这个题目之前，最好能把一个字符串的所有字串的划分实现了。之后可以再此基础上修改，本题提交了开始提交的两次都超时了。看了上面的代码也很长，都是优化过的：

1）首先第一个优化是不要每次都去判断一个字符串是否是回文，把判断过的放进一个map中，是回文value值就标记为true，否则为false；下次先查找此map，如果有就直接返回，否则，调用isPalindrome(String s)方法进行判断，并且加入map中。这个优化的目的，因为字串的重复还是比较多的，不知道这个优化效率提升多少

2）第二个优化是用的剪枝的思想，方法pruning(String s, int depth)实现了这个功能，判断刚加进入的字串是否回文，不是的话，直接返回，就不用在尝试下面的字串了。

但是运行时间还是很长，460ms！

好，再次上个代码，更简洁的：

public ArrayList<ArrayList<String>> partition(String s) {
    		ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
    	 
    		if (s == null || s.length() == 0) {
    			return result;
    		}
    	 
    		ArrayList<String> partition = new ArrayList<String>();
    		addPalindrome(s, 0, partition, result);
    	 
    		return result;
    	}
    	 
    	private void addPalindrome(String s, int start, ArrayList<String> partition,
    			ArrayList<ArrayList<String>> result) {
    		if (start == s.length()) {
    			ArrayList<String> temp = new ArrayList<String>(partition);
    			result.add(temp);
    			return;
    		}
    	 
    		for (int i = start + 1; i <= s.length(); i++) {
    			String str = s.substring(start, i);
    			if (isPalindrome(str)) {
    				partition.add(str);
    				addPalindrome(s, i, partition, result);
    				partition.remove(partition.size() - 1);
    			}
    		}
    	}
    
    	private boolean isPalindrome(String s) {
        	if (s == null || s.isEmpty()) {
        		return false;
        	}
            int i = 0, j = s.length()-1;
            while (i < j) {
            	if (Character.toLowerCase(s.charAt(i++)) != Character.toLowerCase(s.charAt(j--)))
            		return false;
            }
            return true;
        }

这个代码没有使用位向量的方式，这一般就是回溯法的两种方式，都在这里呈现了，这个效率要比之前那个更高。但是发现效率跟其他人比还不是很快，难道还有其他好的解法？好吧，看到我的第一程序用Map优化的方式根本就很长，明显用DP啊。

首先需要递归的填写一张表，这张表存储各个字串是否为回文，比如pair\[i\]\[j\]=true表示sub(i,j)(包括边界i和j)是回文字串，所以可以写出一个递归的解：

if (i == j)  pair\[i\]\[j\]=true（此时为单个字符）

if (i != j) (此时为多个字符) then 需要考虑最后一个字符是否和第一字符相等，即s(i) == s(j)，则pair\[i\]\[j\] =  pair\[i+1\]\[j-1\]，显然此时要保证i+1>= j-1

所以有第三种情况，i == j-1时，pair\[i\]\[j\]=true(此时为两个字符，只需这个字符比较即可，不需要递归调用)。显然，如果s(i) != s(j)那么，pair\[i\]\[j\]=false；所以在O(n^2)的复杂度下，可以把这张表填完，代码示例如下：

for (int i = 0; i < s.length(); i++) {
    			for (int j = 0; j <= i; j++) {
    				if (j == i)
    					pair[j][i] = true;
    				else {
    					if (s.charAt(j) != s.charAt(i))
    						continue;
    					if (j == i - 1)
    						pair[j][i] = true;
    					else
    						pair[j][i] = pair[j + 1][i - 1];
    				}
    			}
    		}

接下来就需要，根据这张表，快速找到符合条件的字串，下面这种事DP+DFS(249ms):

public List<List<String>> partition(String s) {
    		List<List<String>> lists = new ArrayList<>();
    		boolean[][] pair = new boolean[s.length()][s.length()];
    		for (int i = 0; i < s.length(); i++) {
    			for (int j = 0; j <= i; j++) {
    				if (j == i)
    					pair[j][i] = true;
    				else {
    					if (s.charAt(j) != s.charAt(i))
    						continue;
    					if (j == i - 1)
    						pair[j][i] = true;
    					else
    						pair[j][i] = pair[j + 1][i - 1];
    				}
    			}
    		}
    		List<String> partition = new ArrayList<>();
    		addPalindrome(s, 0, partition, lists, pair);
    		return lists;
    	}
    	
    	private void addPalindrome(String s, int start, List<String> partition,
    			List<List<String>> result, boolean[][] pair) {
    		if (start == s.length()) {
    			ArrayList<String> temp = new ArrayList<String>(partition);
    			result.add(temp);
    			return;
    		}
    	 
    		for (int i = start + 1; i <= s.length(); i++) {
    			if (pair[start][i-1]) {
    				String str = s.substring(start, i);
    				partition.add(str);
    				addPalindrome(s, i, partition, result, pair);
    				partition.remove(partition.size() - 1);
    			}
    		}
    	}

复杂度是多少O(n^2) OR O(2^n)

在思考下，根据DP的思想，在生成pair\[\]\[\]的时候，其实我们已经知道怎么组装字符串了，为什么还用回溯，上代码：

public List<List<String>> partition(String s) {
    		@SuppressWarnings("unchecked")
    		List<List<String>>[] lists = new List[s.length()+1];
    		lists[0] = new ArrayList<List<String>>();
    		lists[0].add(new ArrayList<String>());
    		
    		boolean[][] pair = new boolean[s.length()][s.length()];
    		for (int i = 0; i < s.length(); i++) {
    			lists[i+1] = new ArrayList<List<String>>();
    			for (int j = 0; j <= i; j++) {
    				if (j == i) 
    					pair[j][i] = true;
    				else {
    					if (s.charAt(j) != s.charAt(i))
    						continue;
    					if (j == i - 1)
    						pair[j][i] = true;
    					else
    						pair[j][i] = pair[j + 1][i - 1];
    				}
    				if (pair[j][i]) {
    					String str = s.substring(j, i+1);
    					for (List<String> r : lists[j]) {
    						List<String> ri = new ArrayList<>(r);
    						ri.add(str);
    						lists[i+1].add(ri);
    					}
    				}
    			}
    		}
    		return lists[s.length()];
    	}

但是这个是O(n^2)??????