# ECJAN20G - Editorial

Author: arnie8991
Tester: nutella
Editorialist: arnie8991

MEDIUM

Strings, DP/DFS

# EXPLANATION:

The quickest and simplest way to solve this problem is by using the DFS with memoization. Store all the numbers in the input array as strings in a hashset or a map and then for every string check if the substring of this string is present in the hashset or map. Lets say we have a string A of length say n, and we have a function āisValidSubstringā that takes a string as an argument and checks if that substring is present in the hashset or map. The DP equation will be the following.

return True if A[0:a] in hashset || isValidSubstring[a:]

NOTE: This problem can also be implemented with Tries ds.

# SOLUTIONS:

[details=āSetterās Solutionā]

``````import java.util.Scanner;
import java.util.Arrays;
import java.util.*;
import java.io.*;

class Main{

public static void solve(String []input){
List<String> concatenated = new ArrayList<>();
Set<String> hashset = new HashSet<>();

for(String word: input){
}

for(String word:input){
if(isValidSubstring(hashset,word))
}

System.out.println(concatenated.size());
}

public static boolean isValidSubstring(Set<String> hashset, String word){
for (int i = 1; i < word.length(); i++) {
if (hashset.contains(word.substring(0, i))) {
String rightStr = word.substring(i);
if (hashset.contains(rightStr) || isValidSubstring(hashset, rightStr))
return true;
}
}
return false;
}

public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n;
String input[];

n = sc.nextInt();
input = new String[n];
for(int i = 0;i<n;i++){
input[i] = sc.next();
}
solve(input);
}

}``````
1 Like