There's no end to the leetcode questions about finding palindrome pairs and how to determine if a given string is a palindrome, but I can't seen to find any discussion about sentence palindrome testing for unordered words. (Every word must be used in the palindrome for the function to return true)
For instance, on the input:
["stop", "nine", "rum", "myriad", "put", "up", "rum", "dairymen", "murmur", "in", "pots"]
the function would return True, and on:
["sit", "on", "potato", "pan", "otis"]
it would return False.
A naive solution in Python would be to useitertools.permutations(words, len(words)) to check every possible solution, but as word count grows, I believe this is at least O(n!*c) with n words and c characters.
Heap's algorithm doesn't seem to particularly lend itself well to the problem, because a way of generating half of the permutations and short circuiting all the "children" permutations that have the same outer configuration when the first and last words don't start palindromic, doesn't really make itself obvious.
However with the Steinhaus–Johnson–Trotter algorithm, it seems there is a nice delineation at the halfway point in which the permutations repeat essentially in reverse. However I can't think of a way to efficiently "short circuit" cases we don't need to check past that. Perhaps there is some way to skip inversion numbers based off of what cases can be ruled out?
Edit: Here's an example that would be quite hard to crack:
['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111', '11000', '11001', '11010', '11011', '11100', '11101', '11110', '11111', '100000', '100001', '100010', '100011', '100100', '100101', '100110', '100111', '101000', '101001', '101010', '101011', '101100', '101101', '101110', '101111', '110000', '110001', '110010', '110011', '110100', '110101', '110110', '110111', '111000', '111001', '111010', '111011', '111100', '111101', '111110', '111111', '1000000', '1000001', '1000010', '1000011', '1000100', '1000101', '1000110', '1000111', '1001000', '1001001', '1001010', '1001011', '1001100', '1001101', '1001110', '1001111', '1010000', '1010001', '1010010', '1010011', '1010100', '1010101', '1010110', '1010111', '1011000', '1011001', '1011010', '1011011', '1011100', '1011101', '1011110', '1011111', '1100000', '1100001', '1100010', '1100011', '1100100']
As there are about 10^157 permutations. But more reasonably:
['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110', '10111']
would return False but
['1', '10', '11', '100', '101', '110', '111', '1000', '1001', '1010', '1011', '1100', '1101', '1110', '1111', '10000', '10001', '10010', '10011', '10100', '10101', '10110']
would return True, as this palindrome exists:
["1000", "1100", "110", "10100", "10011", "11", "1010", "1101", "1011", "1110", "10000", "10", "1111", "10110", "1", "10101", "111", "100", "10010", "101", "1001", "10001"]
CodePudding user response：
Here's an approach to solving this problem.
Note: This approach is based on the following assumptions:
- A palindrome word pair must be formed from two words of same length
- A palindrome sentence can only be formed from whole words from the list
1. organize the entries in the incoming list into a dictionary where the k = len of words and the value is a list of words. Note this can be done in time O(n)
2. For each key in the dictionary:
a. starting with index = 0, compare inverse of the word to contents of index 1 to index=len(values) -1
if a n equality is found:
return True
else:
increment index and repeat a
3. If all keys have have been searched, return False
The following is a simple implementation of this approach:
from collections import defaultdict
def isPalindromeSentence(word_list: list[str])-> bool:
# return True if a palindrome sentence can be formed from word_list
optsDict = defaultdict(list)
for wrd in word_list:
optsDict[len(wrd)].append(wrd)
for k, vl in optsDict.items():
if len(vl) > 1:
for i in range(1, len(vl)):
if vl[i-1][::-1] in vl[i:]:
return True
return False
CodePudding user response：
Okay, I have been schooled into what constitutes a palindrome sentence and see as @n.m. rightfully pointed out my original solution solved a totally different problem. So Here is a more sophisticated solution to the problem.
If we assume a word list for a palindrome sentence adheres to the following:
- Words included in the sentence must be in the list without alteration
- The palindrome is formed by the sequence of letters forming the sentence with capitalization, spaces and punctuation ignored.
- All words in word_list must be included in the sentence.
then lists such as the following will result in a True result:
['011', '11', '10'] -> '0111110',
['Sit', 'on', 'a', 'potato', 'pan', 'Otis'] -> 'sitonapotatopanotis',
['Ah', 'Satan', 'sees', 'Natasha'] -> 'ahsatanseesnatasha',
['Cigar', 'Toss', 'it', 'in', 'a', 'can', 'It', 'is', 'so', 'tragic'] -> 'cigartossitinacanitissotragic'
From the above we observe the following characteristics:
- the first letter = the last letter, the second letter = the second from last letter etc.
- If we select a word option from word_list, we can eliminate from consideration as the last word any word_list entries that don't contain the same letters as the first word when indexed backwards. Note: If the last word selected is shorter than the first word only letters in last word need to be equal, If the last word is longer than the first word, only letters if first word need to equate.
With the above as a guide the algorithm would follow as:
- select word from word_list to act a the lead phrase
- create new list try_list which has the selected word removed.
- create a data container which contains the lead_phrase, an empty tail_phrase, and the remaining words to check.
- push the data container onto a fifo queue.
- Once all words in word_list have been pushed onto queue as the lead_phrase.
- While queue has an entry:
a. pop a data container from the queue.
b. if the remaining word list is empty:
- combine the lead phrase with the tail phrase and test for palindrome
- if a palindrome return true, else drop the data container c. when remaining word_list is not empty
- determine if we should add a lead phrase or a tail phrase
- select a candidate word from the list, if it exists.
- create a new data container which contains the updated lead phrase, tail phrase and the remianing word list
- push the data container onto the queue
- repeat step 6
- If queue is empty, return False
The following code implements the above algorithm
from dataclasses import dataclass, field
from typing import Optional
def extractItem(inList: list, indx: int) -> list:
# return inList with item at indx removed
return inList[:indx] inList[indx 1:]
def isPalindrome(wrd_list: list[str]) -> bool:
# return True if wrd_list can be organized as a palindrome
for i in range(len(wrd_list)):
wrd_list[i] = wrd_list[i].lower()
que = []
for i in range(len(wrd_list)):
ps = PaliStruct(frtEnd=wrd_list[i],
bckEnd='',
toTry=extractItem(wrd_list, i))
que.append(ps)
while que:
ps = que.pop(0) # pop the que entry
if ps.toTry:
for i in range(len(ps.toTry)):
Lead_Phrase = ps.frtEnd
Tail_Phrase = ps.bckEnd
if len(ps.frtEnd) >= len(ps.bckEnd):
# Adding to Tail_Phrase
Tail_Phrase = ps.toTry[i] Tail_Phrase
else:
# Adding to Lead_Phrase
Lead_Phrase = ps.toTry[i]
tstIndx = min(len(Lead_Phrase), len(Tail_Phrase))
if Lead_Phrase[:tstIndx] == Tail_Phrase[::-1][:tstIndx]:
# found a candidate
px = PaliStruct(frtEnd=Lead_Phrase,
bckEnd=Tail_Phrase,
toTry=extractItem(ps.toTry, i))
que.append(px)
else:
sntc = ps.frtEnd ps.bckEnd
if sntc == sntc[::-1]: # Test for palindrome solution
return True
else:
return False
The following tests were used to validate the accuracy of this solution:
tst1 = ['011', '11', '10']
tst1a = ['10', '011', '11']
tst1b = ['10', '011', '11', '010']
tst2 = ['Cigar', 'Toss', 'it', 'in', 'a', 'can', 'It', 'is', 'so', 'tragic']
tst2a = ['tragic', 'so', 'is', 'It', 'can', 'a', 'in', 'it', 'Toss', 'Cigar']
tst2b = ['tragic', 'so', 'is', 'It', 'can', 'a', 'it', 'Toss', 'Cigar']
tst3 = ['Sit', 'on', 'a', 'potato', 'pan', 'Otis']
tst3a = ['potato', 'a', 'on', 'Otis', 'pan', 'Sit']
tst3b = ['potato', 'a', 'on', 'alpha', 'Otis', 'pan', 'Sit']
tst4 = ['Ah', 'Satan', 'sees', 'Natasha']
tst4a = ['Ah', 'Natasha', 'Satan','sees']
tst4b = ['sees', 'Natasha', 'Satan']
Note all tests of form xxxb produce a False return, while all others produce True returns using the following:
testCases = [tst1, tst1a, tst1b, tst2, tst2a, tst2b, tst3, tst3a, tst3b, tst4, tst4a, tst4b]
for x, test in enumerate(testCases):
print(f'Test {x}: Input: {test} -> {isPalindrome(test)}')
Which produces the following output:
Test 0: Input: ['011', '11', '10'] -> True
Test 1: Input: ['10', '011', '11'] -> True
Test 2: Input: ['10', '011', '11', '010'] -> False
Test 3: Input: ['Cigar', 'Toss', 'it', 'in', 'a', 'can', 'It', 'is', 'so', 'tragic'] -> True
Test 4: Input: ['tragic', 'so', 'is', 'It', 'can', 'a', 'in', 'it', 'Toss', 'Cigar'] -> True
Test 5: Input: ['tragic', 'so', 'is', 'It', 'can', 'a', 'it', 'Toss', 'Cigar'] -> False
Test 6: Input: ['Sit', 'on', 'a', 'potato', 'pan', 'Otis'] -> True
Test 7: Input: ['potato', 'a', 'on', 'Otis', 'pan', 'Sit'] -> True
Test 8: Input: ['potato', 'a', 'on', 'alpha', 'Otis', 'pan', 'Sit'] -> False
Test 9: Input: ['Ah', 'Satan', 'sees', 'Natasha'] -> True
Test 10: Input: ['Ah', 'Natasha', 'Satan', 'sees'] -> True
Test 11: Input: ['sees', 'Natasha', 'Satan'] -> False