百度网站联盟,公司做网站一般用什么域名,开原网站网站建设,西宁网络信息 网站建设131 Palindrome Partitioning 输入一个字符串s#xff0c;将s分割为n个子串#xff0c;每个子串都是一个回文。返回s有多少种分割方式。 例如输入#xff1a;“aab” 输出#xff1a;[ [“aa”,”b”], [“a”,”a”,”b”] ] 思路#xff1a;这是一个不断将问…131 Palindrome Partitioning 输入一个字符串s将s分割为n个子串每个子串都是一个回文。返回s有多少种分割方式。 例如输入“aab” 输出[ [“aa”,”b”], [“a”,”a”,”b”] ] 思路这是一个不断将问题规模变小的问题。有点动态规划的味道。 问题1 对”aab”切分子串。首先可以看做是 “a” 和”ab”切分。第一部分”a”切分确定并且”a”是一个回文”ab”作为输入字符串再次回到原问题。 问题1-1 对”ab”切分子串。不断递归直到输入字符串为0。 再次回到问题1。第二可以看做是 “aa” 和”b”切分。第一部分”aa”切分确定并且”aa”是一个回文”b”作为输入字符串再次回到原问题。 问题1-2 对”b”切分子串。 …..不断下去。
partition(“abc”) [ “a” partition(“bc”)] [ “aa” partition(“c”)] [ “aab” partition(“”)] partition(“bc”)[“b”partition(“c”)] partition(“c”)”c” partition(“”) 添加答案直接退出。 private ListListString resultList new ArrayListListString();public ListListString partition(String s) {resultList.clear();doPartition(s,new ArrayListString());return resultList;}private void doPartition(String s,ListString result){if(s){ListString n new ArrayListString();n.addAll(result);resultList.add(n);return;}int startIdx 0;for(int endIdx 1;endIdxs.length();endIdx){String subString s.substring(startIdx,endIdx);if(isPalindrome(subString)){result.add(subString);doPartition(s.substring(endIdx),result);result.remove(result.size()-1);}}if(isPalindrome(s)){result.add(s);doPartition(,result);result.remove(result.size()-1);}}private boolean isPalindrome(String s){int mid s.length()/2;int end s.length()-1;for(int i0;imid;i){if(s.charAt(i)!s.charAt(end-i)){return false;}}return true;}
改进 思路一模一样只是在处理的时候尽量少使用String的substring方法。参考链接。substring会创建一个新的String对象同时有一个数组拷贝的动作。该版本的速度大大提升。 private ListListString resultList new ArrayListListString();public ListListString partition(String s) {resultList.clear();doPartition(s,0,new ArrayListString());return resultList;}private void doPartition(String s,int leftIdx,ListString result){if(leftIdxs.length()){ListString n new ArrayListString();n.addAll(result);resultList.add(n);return;}for(int endIdx leftIdx;endIdxs.length();endIdx){if(isPalindrome(s,leftIdx,endIdx)){result.add(s.substring(leftIdx,endIdx1));doPartition(s,endIdx1,result);result.remove(result.size()-1);}}}private boolean isPalindrome(String s,int l,int r){if(lr) return true;while(lr){if(s.charAt(l)!s.charAt(r)){return false;}l;r--;}return true;}
