乐趣区

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

jiezi

一个字符串能够分解成多种二叉树构造。如果 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 多平台公布

退出移动版