Tags: "leetcode", "dynamic-programming", access_time 1-min read

Edit this post on Github

Concatenate String Using Smaller Strings

Created: December 9, 2019 by [lek-tin]

Last updated: December 9, 2019

Given a big string and a list of small strings, find whether the big string can be represented only by concatenation of smaller strings.


target = "abccbacbb"
smallerStrings = ["abc", "cc", "ab", "bac", "b"]
Output: True


Dynamic programming

target = "abccbacbb"
smallerStrings = ["abc", "cc", "ab", "bac", "b"]

N = len(target)
dp = [False for _ in range(N)]

def check(i, target):
  for s in smallerStrings:
    l = len(s)
    # print(s)
    if i + l <= N:
      tryStr = target[i:i+l]
      # print(tryStr)
      if tryStr == s:
        dp[i+l-1] = True
        check(i+l, target)
    # print("-------")

check(0, target)