乐趣区

关于程序员:每日一题旋变字符串

一个字符串能够分解成多种二叉树构造。如果 str 长度为 1,认为不可合成。如果 str 长度为 N(N > 1), 左局部长度可 认为 1 ~ N – 1,剩下的为右局部的长度。左局部和右局部都能够依照同样的逻辑,持续合成。造成的所有构造都是 str 的二叉树构造。

比方,字符串“abcd”,能够分解成一下五种构造:

任何一个 str 的二叉树构造中,如果两个节点有独特的父节点,那么这两个节点能够替换位

置,这两个节点叫作一个替换组。一个构造会有很多替换组,每个替换组都能够抉择进行交

换或者不替换,最终造成一个新的构造,这个新构造所代表的字符串叫作 str 的旋变字符串。

比方,在下面的构造五中,替换组有 a 和 b、ab 和 c、abc 和 d。如果让 a 和 b 的组替换;让 ab 和

c 的组不交 换;让 abc 和 d 的组替换,造成的构造如图

这个新构造所代表的字符串为 ”dbac”,叫作 ”abcd” 的旋变字符串。也就是说,一个字符串

str 的旋变字符串是十分多的,str 能够造成很多种构造,每一种构造都有很多替换组,每

一个替换组都能够抉择替换或者不替换,造成的每一个新的字符串都叫 str 的旋变字符串。

给定两个字符串 str1 和 str2,判断 str2 是不是 str1 的旋变字符串。

解法一:暴力递归

剖析:

str2 是 str1 的旋变字符串必须满足一下条件:

  1. len(str1) == len(str2)
  2. str1 和 str2 的字符品种必须雷同。
  3. str1 和 str2 的每种字符的个数必须雷同。

依据以上三个条件,咱们能够写一个过滤器。

def valid(str1, str2):
    if len(str1) != len(str2): return False

    map1 = {}
    for i in range(len(str1)):
        map1[str1[i]] = map1.get(str1[i], 0) + 1

    for i in range(len(str2)):
        num = map1.get(str2[i], 0)
        num -= 1
        if num < 0: return False
        map1[str2[i]] = num

    return True

尝试模型是:范畴上尝试

判断 $str[L_1…R_1]$ 和 $str[L_2…R_2]$ 是不是互为旋变字符串。

此种尝试计划:有四个参数:$L_1,R_1,L_2,R_2$

依据上边过滤器的条件,咱们晓得 $str[L_1…R_1]$ 和 $str[L_2…R_2]$ 要是互为旋变字符串,长度必须相等。因而,咱们能够将将参数压缩成三个:$L_1,L_2,K$,k 是 str1 的长度。

$f(L_1,L_2,K)$ 示意 判断 $str[L_1…K+L_1]$ 和 $str[L_2…K+L_2]$ 是不是互为旋变字符串。

最终返回后果:f(0, 0, len(arr) – 1)

Base case

  • 如果 k ==1 只有一个字符,只有 $str1[L_1]= str2[L_2]$

如下图:第一刀在 str 中每一个地位进行尝试,每一刀分隔出的两局部进行比对(调用子过程),须要替换后再比对(调用子过程)。

只有有一部分是互为旋变字符串,就返回 true。否则持续尝试第二刀,第三刀 …

def is_scramble(str1, str2):
    if not str1 and not str2: return True
    if (not str1 and str2) or (str1 and not str2): return False
    if str1 == str2: return True
    if not valid(str1, str2): return False
    return f(str1, str2, 0, 0, len(str1))

def f(str1, str2, l1, l2, k):
    if k == 1: return str1[l1] == str2[l2]

    for i in range(1, k):
        res = (f(str1, str2, l1, l2, i) and f(str1, str2, l1 + i, l2 + i, k - i)) or \
              (f(str1, str2, l1, l2 + k - i, i) and f(str1, str2, l1 + i, l2, k - i))
        if res: return True

    return False

解法二:动静布局

  • $k \in (1,n] $
  • $L_1,L_2 \in(0,n)$

本地依赖关系不好梳理,然而原问题的 k,和依赖的子问题的 k’的关系是:k‘< k。所以在填充以后层数据时,只依赖下边层的数据,不依赖本次层数据。dp 表填充程序,从下向上填写。

base case 是 k ==1 时,$dp[1][l_1][l_2] = str1[l_1] == str2[l_2]$

def is_scramble2(str1, str2):
    if not str1 and not str2: return True
    if (not str1 and str2) or (str1 and not str2): return False
    if str1 == str2: return True
    if not valid(str1, str2): return False

    n = len(str1)
    dp = []
    for i in range(n + 1):
        dp.append([[False] * n for _ in range(n)])

    for l1 in range(n):
        for l2 in range(n):
            dp[1][l1][l2] = str1[l1] == str2[l2]

    for k in range(2, n + 1):
        for l1 in range(0, n - k + 1):
            for l2 in range(0, n - k + 1):
                for i in range(1, k):
                    if (dp[i][l1][l2] and dp[k - i][l1 + i][l2 + i]) or \
                            (dp[i][l1][l2 + k - i] and dp[k - i][l1 + i][l2]):
                        dp[k][l1][l2] = True
                        break

    return dp[n][0][0]

本文由 mdnice 多平台公布

退出移动版