从子字符串列表构造目标字符串

Question

我正在做一个小项目，我需要安排现有的子字符串来输出目标字符串。不过，我在处理一个特定案例时遇到了麻烦。假设我想造句：

“棕狐很酷。”

我得到了输入

[“棕色狐狸”、“The”、“棕色”、“很酷”]

如果我天真地实施这个，我会一个字一个字地开始形成“The”+“Brown”，结果发现我实际上不得不从“The Brown Fox”开始。也可能是无法创建目标字符串。

这听起来有点像动态规划，但我在将其形式化和处理上面提到的两种情况时遇到了麻烦。有人介意给我一些帮助，或者指出我可以阅读类似问题的地方吗？

Answer 1

首先让我们举个例子来更好地理解：

示例 1：

输入：

target = "棕色的狐狸很酷。"

arr = ["The brown fox", "The", "brown", "is cool"]

输出：

正确

示例 2：

输入：

target = "棕色的狐狸很酷。"

arr = ["The brown", "The", "brown", "is cool"]

输出：

错

示例 3：

输入：

target = "棕色的狐狸很酷。"

arr = ["棕色狐狸是", "The", "棕色狐狸", "很酷"]

输出：

正确

解释：

即使你总是选择最大的匹配子串，你也不会得到正确答案。

递归方法：

第 1 步： 使用您当前的索引与列表的字符串匹配，即 arr.

Step-2:对于arr的每个元素，首先你必须匹配索引中的目标字符串。

Step-3:如果匹配，则需要查找是否可以通过增加其索引来匹配剩余的目标字符串。

Step-4: 因此在递归结束时，你会根据他们的 return值。

Python代码：

def match_string(string, target, index):
    lens = len(string)
    lent = len(target)
    
    if(index + lens > lent):
        return False
    
    for i in range(index,index+lens):
        if(string[i-index] != target[i]):
            return False
    
    if(target[index+lens] == " " or target[index+lens] == "."):
        return True
    else:
        return False

    
def solve(arr,target,index):
    
    n = len(arr)
    ln = len(target)
    
    if(index == ln):
        return True
    elif(index > ln):
        return False
    
    result = False
    for em in arr:
        if(match_string(em,target,index)):
            result = result or solve(arr,target,index+len(em)+1)
    return result
   

target = "The brown fox is cool."
arr    = ["The brown", "The", "brown","fox", "is cool"]
answer = solve(arr,target,0)

动态编程方法：

只需使用索引来记住每一步递归的结果。

def match_string(string, target, index):
    lens = len(string)
    lent = len(target)
    
    if(index + lens > lent):
        return False
    
    for i in range(index,index+lens):
        if(string[i-index] != target[i]):
            return False
    
    if(target[index+lens] == " " or target[index+lens] == "."):
        return True
    else:
        return False

    
def solve(arr,target,index,dp):
    
    n = len(arr)
    ln = len(target)
    
    if(index == ln):
        return True
    elif(index > ln):
        return False
    
    if(dp[index] != None):
        return dp[index]
    
    result = False
    for em in arr:
        if(match_string(em,target,index)):
            result = result or solve(arr,target,index+len(em)+1,dp)
    dp[index] = result
    return dp[index]
    

target = "The brown fox is cool."
arr    = ["The brown fox", "The", "brown", "is cool"]
dp = [None for i in range(len(target))]
answer = solve(arr,target,0,dp)
print(answer)

从子字符串列表构造目标字符串

Construct a target string from a list of substrings

algorithm

dynamic-programming