My algorithm solves a custom string problem but it loops twice making it $O(n^2)$ time. I'm asking here as I'm a beginner in self-learning algorithms.
Decision Problem: Given an input list $A$, can our target string $S$ be made from any of the elements of $A$?
If just one element does not exist in $A$ (which exists in $s$) then the algorithm returns false.
A = input_array s = input_target_array for i in s: if i in A: (all elements ∈ s) ∈ A else: break (if any element ∈ s) ∉ A: return False else: return True
Enter your input for A and include spaces: Enter letters WITH SPACES: "ab" "cd" "ac" enter your input for s: "abxd" ^ False ^ "abcd" ^ True ^
I'm looking for an algorithm that solves my made up decision problem faster than $O(n^2)$ time.
Are there any methods that can be used from an algorithmic standpoint that would make this $O(n)$ time?