Python Wordle: determine if a given string matches to a correct anagram based on position score

Question

Let assume I have a word

word = abcde

And a score board to show that the position of the characters in the word is correct or not in comparison to my desired output

score = [T, F, F, T, F]

Where T is for correct position, F is for incorrect. So we will have possible output to be acedb and aebdc.
Now given a list of words

words = [abcde, aaaaa, ababa, acedb, bbced]

Based on the scorer above, I would like to find if in the list 'words' exist the correct anagram of word, which is in this case acedb and returns it

output = [acedb]

How can I achieve this with efficient time complexity ? Can I do this in linear time ?

I don't want to use in-built functions, libraries or set/dict (hash tables) as they might screw up my complexity for further tasks so any help would be appriciated

Answer 1

Permute all characters with F and check the string so that we don't introduce any new T's.

Example: word = abcde, score = [T, F, F, T, F]

1. Find all permutations of characters with F's i.e. b,c,e.
2. For each permutation compare the string with word so that we don't introduce any new T's and return the list.

For permutation b,e,c: abedc is not valid anagram as it will have score [T,T,F,T,F].

For permutation e,b,c: aebdc is valid anagram as it will have score [T,F,F,T,F]

Let n be the number of F's in score. Time complexity would be O(n! * n).

In worst case, n = length of the word say N. So, O(N! * N).

---

Not sure how you manage to pull off this in O(N^2). Also, not sure why you think using in-built functions, libraries or set/dict (hash tables) might screw up the complexity. Anyways, hope it helped.