中级农民
- 积分
- 134
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-2-23
- 最后登录
- 1970-1-1
|
palindrome pair, 贴一个我写的很撮的程序:
抛砖引玉:求指点。- import java.util.HashMap;
- import java.util.List;
- import java.util.ArrayList;
- import java.util.Map;
- import java.util.Iterator;
- import java.util.Set;
- import java.util.HashSet;
- public class PalindromePairs {
- public static List<String> palinPair(String[] arr) {
- List<String> palin = new ArrayList<String>();
- if(arr == null || arr.length == 1) return palin;
- TreeNodeInTrie root = buildTree(arr);
- for(String s : arr) {
- String rev = (new StringBuffer(s)).reverse().toString();
- TreeNodeInTrie curr = root;
- StringBuffer sb = new StringBuffer();
- int i = 0;
- boolean cont = true;
- Set<String> finished = new HashSet<String>();
- finished.add(s);
- for(; i < rev.length(); ++i) {
- if(curr.isWord && isPalindrome(s, i, rev.length() - 1)) {
- if(finished.add(sb.toString()))
- palin.add(sb.toString() + ":"+s);
- }
-
- if(curr.child != null && curr.child.containsKey(rev.charAt(i))) {
- curr = curr.child.get(rev.charAt(i));
- sb.append(rev.charAt(i));
- }else{
- cont = false;
- break;
- }
- }
- if(cont) {
- if(i < rev.length()){ //curr is a leaf of the trie tree
- if(isPalindrome(rev, i, rev.length() - 1)) {
- if(finished.add(sb.toString()))
- palin.add(sb.toString() + ":"+s);
- }
- }else{ //curr is not a leaf of the trie tree
- if(curr.isWord) {
- if(finished.add(sb.toString()))
- palin.add(sb.toString() + ":"+s);
- }
- if(curr.child != null){
- List<String> rem = new ArrayList<String>();
- dfs(curr, rem, new StringBuffer());
- for(String s1: rem) {
- if(isPalindrome(s1,0, s1.length() - 1)) {
- if(finished.add(sb.toString() + s1))
- palin.add(sb.toString()+s1+":"+ s);
- }
- }
- }
- }
- }
- }
-
- return palin;
- }
-
- private static void dfs(TreeNodeInTrie curr, List<String> rem, StringBuffer sb){
- if(curr.child == null) {
- return;
- }
- Iterator<Character> its = curr.child.keySet().iterator();
- while(its.hasNext()){
- char ch= its.next();
- sb.append(ch);
- if(curr.child.get(ch).isWord) rem.add(new String(sb));
- dfs(curr.child.get(ch), rem, sb);
- sb.deleteCharAt(sb.length() - 1);
- }
- }
-
-
- private static boolean isPalindrome(String s, int i, int j) {
- if(i >= j) return true;
- while(i < j) {
- if(s.charAt(i) != s.charAt(j)) return false;
- ++i;
- --j;
- }
- return true;
- }
-
- private static TreeNodeInTrie buildTree(String[] arr){
- TreeNodeInTrie root = new TreeNodeInTrie(' ', false);
- for(String s : arr) {
- int len = s.length();
- TreeNodeInTrie curr = root;
- for(int i = 0; i < len; ++i) {
- if(curr.child == null){ //child is empty, create child and a new TreeNodeInTrie
- Map<Character, TreeNodeInTrie> child = new HashMap<Character, TreeNodeInTrie>();
- curr.child = child;
- }
-
- if(curr.child.containsKey(s.charAt(i))) { //if the TreeNodeInTrie exists;
- if(i == len - 1) curr.child.get(s.charAt(i)).isWord = true;
- }else{ //if the TreeNodeInTrie does not exists
- curr.child.put(s.charAt(i), new TreeNodeInTrie(s.charAt(i), i == len - 1));
- }
- curr = curr.child.get(s.charAt(i)); // recursively
- }
- }
- return root;
- }
-
-
- public static void main(String[] args) {
- String[] arr = new String[] {"a", "aa", "aaa"};
- System.out.println(palinPair(arr));
- String[] arr1 = new String[] {"shit", "tihsa"};
- System.out.println(palinPair(arr1));
- }
- }
- class TreeNodeInTrie {
- char c;
- Map<Character, TreeNodeInTrie> child;
- boolean isWord;
- TreeNodeInTrie(char c, boolean isWord){
- this.c = c;
- this.isWord = isWord;
- }
- }
复制代码
补充内容 (2014-11-6 03:28):
给的两个例子跑出来的结果是:
[aa:a, aaa:a, a:aa, aaa:aa, a:aaa, aa:aaa]
[tihsa:shit]
|
|