The DNA Sequence Splitter
A bioinformatician needs to split a DNA sequence into valid gene segments. The DNA sequence contains only characters 'A', 'C', 'G', and 'T'.
A segment is valid if it matches one of the known gene patterns. You are given k known patterns.
Find the minimum number of segments needed to completely split the DNA sequence using only valid patterns. Patterns can be reused.
If the sequence cannot be completely split, return -1.
Input Format
The first line contains the DNA sequence string s. The second line contains an integer k, the number of known patterns. The next k lines each contain a pattern string.
Output Format
Print the minimum number of segments, or -1 if impossible.
Examples
Example 1
Example 2
Constraints
•
1 ≤ length of s ≤ 1000
•
1 ≤ k ≤ 100
•
1 ≤ length of each pattern ≤ 100
•
All strings contain only A, C, G, T
Code
Case 1
Case 2