class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        HashMap<String, Integer> map = new HashMap();

        for (int i = 0; i < words.length; i++){
            map.put(words[i], i);
        }

        List<List<Integer>> result = new ArrayList<>();

        //fucking case of the empty string
        if (map.containsKey("")) {
            int emptyIndex = map.get("");

            for (int i = 0; i < words.length; i++) {
                if (i != emptyIndex && isPalindrome(words[i])) {
                    result.add(Arrays.asList(emptyIndex, i));
                    result.add(Arrays.asList(i, emptyIndex));
                }
            }
        }

        //just a direct reverse
        for (int i = 0; i < words.length; i++) {
            findSupplementString(map, result, words[i], i, true);
        }

        //looking for left and right candidates
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int wordLength = word.length();
            for(int j = 1; j < wordLength; j++){
                String leftPart = word.substring(0, j);
                String rightPart = word.substring(j);

                if(isPalindrome(leftPart)){
                    findSupplementString(map, result, rightPart, i, false);
                }

                if(isPalindrome(rightPart)){
                    findSupplementString(map, result, leftPart, i, true);
                }
            }
        }

        return result;

    }

    private void findSupplementString(HashMap<String, Integer> map, List<List<Integer>> result, String candidate,  int candidateIndex, boolean candFirst){
        String reversedWord = new StringBuilder(candidate).reverse().toString();

        if (map.containsKey(reversedWord)){
            int newIndex = map.get(reversedWord);
            if(candidateIndex != newIndex) {

                if(candFirst) {
                    result.add(Arrays.asList(candidateIndex, newIndex));
                }
                else
                    result.add(Arrays.asList(newIndex, candidateIndex));
            }
        }
    }

    private boolean isPalindrome(String s){
        int l = 0;
        int r = s.length() - 1;
        char[] charArray = s.toCharArray();
        while(l <= r){
            if(charArray[l] != charArray[r]){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }

}