Find Combined Service Tags
A delivery company maintains a list of service tags. Some longer tags are created by joining two or more other tags from the same list without spaces.
Find all tags that can be formed completely by joining other available tags.
Implement the following method:
List<String> findCombinedTags(List<String> serviceTags)
serviceTags contains the available service tags.- The method returns every tag that can be formed by joining at least two other tags from the list.
- Return the valid tags in the same order in which they appear in
serviceTags.
Rules
- Every character of a combined tag must belong to one of its component tags.
- At least two component tags must be used.
- A component tag may be used more than once.
- A tag cannot use itself as its only component.
- If a tag has multiple valid combinations, include it only once in the result.
Constraints
1 ≤ serviceTags.size() ≤ 10,0001 ≤ serviceTags.get(i).length() ≤ 1,000- The combined length of all tags does not exceed
100,000.
- Every tag contains lowercase English letters only.
- All tags are unique.
- Neither
serviceTags nor any tag inside it will be null.
Examples
Example 1
findCombinedTags( serviceTags = List.of( "morning", "delivery", "morningdelivery", "door", "step", "doorstep", "express", "expressdoorstep" ) )
Output: List.of("morningdelivery", "doorstep", "expressdoorstep")
"morningdelivery" is formed from "morning" and "delivery". "doorstep" is formed from "door" and "step". The final returned tag is formed from "express", "door", and "step".
Example 2
findCombinedTags( serviceTags = List.of( "eco", "ship", "ecoship", "plus", "ecoshipplus", "rapid" ) )
Output: List.of("ecoship", "ecoshipplus")
"ecoship" is formed from "eco" and "ship". "ecoshipplus" can be formed from "eco", "ship", and "plus".
Example 3
findCombinedTags( serviceTags = List.of( "local", "rapid", "secure", "direct" ) )
Output: List.of()
No tag can be formed by joining two or more other tags from the list.