Python solution~


  • 22
    Z
        wordict = {}
        res = [] 
        for i in range(len(words)):
            wordict[words[i]] = i
        for i in range(len(words)):
            for j in range(len(words[i])+1):
                tmp1 = words[i][:j]
                tmp2 = words[i][j:]
                if tmp1[::-1] in wordict and wordict[tmp1[::-1]]!=i and tmp2 == tmp2[::-1]:
                    res.append([i,wordict[tmp1[::-1]]])
                if j!=0 and tmp2[::-1] in wordict and wordict[tmp2[::-1]]!=i and tmp1 == tmp1[::-1]:
                    res.append([wordict[tmp2[::-1]],i])
                    
        return res

  • 3
    G

    You could probably simplify this a bit with a dict comprehension

    worddict = {word:i for i, word in enumerate(words)}

    And the outer loop could be made:

    for i, word in enumerate(words):

    It'll save you from having to index words multiple times throughout the body of the for loop (words[i])


  • 0
    C

    That's useful. Thanks for pointing that out!


  • 0
    R

    really nice and easy to understand solution, I translated to c++ at (c++)[https://leetcode.com/discuss/92875/accepted-simple-c-solution]


  • 10
    T

    Nice code! Just typing out grodrigues3's suggestions:

    def palindromePairs(self, words):
        d, res = dict([(w[::-1], i) for i, w in enumerate(words)]), []
        for i, w in enumerate(words):
            for j in xrange(len(w)+1):
                prefix, postfix = w[:j], w[j:]
                if prefix in d and i != d[prefix] and postfix == postfix[::-1]:
                    res.append([i, d[prefix]])
                if j>0 and postfix in d and i != d[postfix] and prefix == prefix[::-1]:
                    res.append([d[postfix], i])
        return res 

  • 0
    S
    This post is deleted!

  • 0
    S

    Great solution, but I have some questions: 1) why does your j loop go until len(w)+1 instead of just len(w)? Wouldn't that risk an out of bounds error? 2) What is the purpose of having the if checks postfix == postfix[::-1] and prefix == prefix[::-1]? What special palindrome case is that trying to handle?


  • 1
    K

    Because they are using only xrange to get the offsets and not actually the elements. In that case J in w[:J] is not inclusive and wouldn't fail. Try a = 'abc' a[:100], it will return 'abc' without fail.


  • 1

    Thx. This is what Python wants to present.


  • 0
    This post is deleted!

  • 0
    B

    Will the time complexity be O(n*L^2)? n is the number of words in the dict, L is the average length of each word.


  • 0
    P
    This post is deleted!

  • 0
    W

    @bing28 Agree with you.


  • 0
    W

    @pyqt To avoid duplicates in final results. See explanation here: https://discuss.leetcode.com/topic/39584/accepted-python-solution-with-explanation


  • 0
    L

    @totolipton I am not sure why the tuples are in an array.
    could:
    d, res = dict([(w[::-1], i) for i, w in enumerate(words)]), []
    be rewritten as:
    d, res = dict((w[::-1], i) for i, w in enumerate(words)), [] ?


  • -1
    P

    This code can be further optimized by using wordict.get() instead of searching for prefix/suffix by iterating through dictionary keys.
    The get() method returns None if the key is not found and it's time complexity is O(1).

    Rewriting @totolipton's code :

    def palindromePairs(self, words):
        d, res = dict([(w[::-1], i) for i, w in enumerate(words)]), []
        for i, w in enumerate(words):
            for j in xrange(len(w)+1):
                prefix, postfix = w[:j], w[j:]
                if d.get(prefix) and i != d[prefix] and postfix == postfix[::-1]:
                    res.append([i, d[prefix]])
                if j>0 and d.get(postfix) and i != d[postfix] and prefix == prefix[::-1]:
                    res.append([d[postfix], i])
        return res 
    

  • 0
    L

    @praveen47 did you even try to run this?


Log in to reply
 

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