北京望京SOHO-电商墨镜面试题

我去面试,boos 给出了个。动态规划的题目:

‘’‘’‘’

A = "asdf"
B = "axazxcv"

S = "axasazdxfcv"

字符串A 和 字符串B A 和 B 拆散组合成 S。 但是相对位置上不能变。
判断 S 这个字符串,是否是由 AB 组成并且 相对位置不变, 如果是 返回Ture 否则False

##注:A串 和 B串。 是有重复的的字符的。 暂且忽略特殊字符的问题。
例:
  A = "asdf"
  B = "axazxcv"
  S = "axasazdxfcv"
  return Ture
  =============================================
  A = "asdf"
  B = "axazxcv"
  S = "xaasazdxfcv"
  return False

初一判断 我当时的想法完全是错的。  以下的是回家的路上想到的。

1. 因为重复的问题,所以就不能单单的只靠 一个字符单纯的判断, S串中的某一个字符, 是属于A的还是属于B的。

2. 所以一定是 S 的当前,某一个字符时,要判断一下 他前面的那个字符,是A的还是B的。

可以这样去理解:

A 表示为 A[0:i]      B 表示为 B[0:j]

S[0:i+j]   ==   A[0:i] + B[0:j]   ##(这里不是字符串拼接,)

A = "asdf"
B = "axazxcv"

S = "axasazdxfcv"

def static(A, B, S):
    if len(A+B) != len(S):  # 首先判断 两个的长度,是否相同。
        return False
    a = len(A)+1
    b = len(B)+1
   # 初始化二维列表。 li = [[[] for _ in range(a)] for _ in range(b)] li[0][0] = True for i in range(1, a): li[0][i] = li[0][i-1] and A[i-1] == S[i-1] for j in range(1, b): li[j][0] = li[j-1][0] and B[j-1] == S[j-1]
  # 以上两部做的事情 可以看下面的图:   # 这里才是开始计算 for i in range(1, a): for j in range(1, b): li[j][i] = (li[j][i-1] and A[i-1] == S[i+j-1]) or (li[j-1][i] and B[j-1] == S[i+j-1]) for n in li: print(n) return li[j][i]

 

以下是 运行的结果。


print(static(A, B, S))

[True, True, False, False, False] [True, False, False, False, False] [True, True, True, False, False] [True, False, True, False, False] [False, False, True, True, False] [False, False, False, True, True] [False, False, False, False, True] [False, False, False, False, True] True

 

 

           a      s     d      f   
  [True, True, False, False, False] a [True, [], [], [], []] x [True, [], [], [], []] a [True, [], [], [], []] z [False, [], [], [], []] x [False, [], [], [], []] c [False, [], [], [], []] v [False, [], [], [], []]

# 这里就是判断出S这个字符串的 前A的长度位上,于A有几个相同,显示在 第一行。
# 前B 长度上,与B有几个相同。 显示在一列上。
# 通过这个 应该就能看出, S这个字符串第一个位置上的字符, 是和 A 相同还是 B相同。 我的例子上,是两个都相同

然后接下来就是 不好理解的地方了。
从 S 这个字符串第二个索引的位置开始,判断一下这个位置上的字符,是来自A[0-i]的某一个,还是来自B[0-j]的某一个。并且要与前一个字符进行比较。
比如:
  S的第二个字符x 他是属于B这个串的,B这个串中 a 字符的位置是在,数组中li[j][i-1]的这个位置上。 S的第二个字符如果是 a 的话,那他就属于
  A这个串的,在 li[j][i] 这个位置上就应该是 Ture。 但是他不属于。 所以是 False

问题的关键就是,把他理解成, 将 A 这个字符串拆散,然后随机的插入到了 B这个串的某一个位置上。
然后 我们循环 去确定S这个串上的每一个字符, 与 A或者B 对应位置上的某个字符相等。再加上与前面结果的 比较。 只有前面的是 Ture的情况下,S的当前
的某个字符,才能够是Ture。 否则就是 False。

这样 一级一级的判断下去,到最后一个的时候,如何使Ture 那个整个字符串就是 匹配的, 否则就是不匹配。

上一篇:Android 播放网络视频的网页浏览器


下一篇:leetcode 884. 两句话中的不常见单词(Uncommon Words from Two Sentences)