Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class Solution {
- public List<List<Integer>> palindromePairs(String[] words) {
- List<List<Integer>> res = new ArrayList<List<Integer>>();
- if(words == null || words.length == 0){
- return res;
- }
- //build the map save the key-val pairs: String - idx
- HashMap<String, Integer> map = new HashMap<>();
- for(int i = 0; i < words.length; i++){
- map.put(words[i], i);
- }
- //special cases: "" can be combine with any palindrome string
- if(map.containsKey("")){
- int blankIdx = map.get("");
- for(int i = 0; i < words.length; i++){
- if(isPalindrome(words[i])){
- if(i == blankIdx) continue;
- res.add(Arrays.asList(blankIdx, i));
- res.add(Arrays.asList(i, blankIdx));
- }
- }
- }
- //find all string and reverse string pairs
- for(int i = 0; i < words.length; i++){
- String cur_r = reverseStr(words[i]);
- if(map.containsKey(cur_r)){
- int found = map.get(cur_r);
- if(found == i) continue;
- res.add(Arrays.asList(i, found));
- }
- }
- //find the pair s1, s2 that
- //case1 : s1[0:cut] is palindrome and s1[cut+1:] = reverse(s2) => (s2, s1)
- //case2 : s1[cut+1:] is palindrome and s1[0:cut] = reverse(s2) => (s1, s2)
- for(int i = 0; i < words.length; i++){
- String cur = words[i];
- for(int cut = 1; cut < cur.length(); cut++){
- if(isPalindrome(cur.substring(0, cut))){
- String cut_r = reverseStr(cur.substring(cut));
- if(map.containsKey(cut_r)){
- int found = map.get(cut_r);
- if(found == i) continue;
- res.add(Arrays.asList(found, i));
- }
- }
- if(isPalindrome(cur.substring(cut))){
- String cut_r = reverseStr(cur.substring(0, cut));
- if(map.containsKey(cut_r)){
- int found = map.get(cut_r);
- if(found == i) continue;
- res.add(Arrays.asList(i, found));
- }
- }
- }
- }
- return res;
- }
- public String reverseStr(String str){
- StringBuilder sb= new StringBuilder(str);
- return sb.reverse().toString();
- }
- public boolean isPalindrome(String s){
- int i = 0;
- int j = s.length() - 1;
- while(i <= j){
- if(s.charAt(i) != s.charAt(j)){
- return false;
- }
- i++;
- j--;
- }
- return true;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement