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
Output
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.
Question
Are there any methods that can be used from an algorithmic standpoint that would make this $O(n)$ time?
(all elements ∈ s) ∈ A
mean in code? $\endgroup$ – user253751 Jan 22 '20 at 12:55