O(n) iterative solution


  • 0
    H

    Inspired by a recursive solution, I came up with the iterative version.

    public String shortestPalindrome(String s) {
    
            int left = 0;
            int right = s.length() - 1;
            int index = right;
            Deque<String> stack = new LinkedList<>();
    
            while (left < index) {
                right = index;
                for (;right >= 0; right--) {
                    if (s.charAt(left) == s.charAt(right)) {
                        ++left;
                    }
                }
                if (left == index + 1) {
                    break;
                }
                String suffix = s.substring(left, index + 1);
                stack.push(new StringBuilder(suffix).reverse().toString());
                // Reset search space
                index = left - 1;
                left = 0;
            }
    
            String prefix = "";
            while (!stack.isEmpty()) {
                prefix = stack.pop() + prefix;
            }
            return prefix + s;
        }
    

  • 0

    What makes you think that that's O(n)?


  • 0
    H

  • 0

    @huangbow What about it? That's not O(n). As already shown right there in that topic.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.