package jjn.carl.dp;
import java.util.*;
/** * @author Jjn * @since 2023/8/21 10:46 */public class LeetCode139 {    public boolean wordBreak(String s, List<String> wordDict) {        boolean[] dp = new boolean[s.length() + 1];        dp[0] = true;        Set<String> set = new HashSet<>(wordDict);        for (int i = 0; i <= s.length(); i++) {            for (int j = 0; j < i; j++) {                if (dp[j] && set.contains(s.substring(j, i))) {                    dp[i] = true;                    break;                }            }        }        return dp[s.length()];    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int count = scanner.nextInt();        List<String> wordDict = new ArrayList<>(count);        for (int i = 0; i < count; i++) {            wordDict.add(scanner.next());        }        String s = scanner.next();        boolean wordBreak = new LeetCode139().wordBreak(s, wordDict);        System.out.println(wordBreak);    }}