string - 如何编写一个接受字符串并返回最长有效子字符串的方法

Question

我一直在和一个 friend 练习面试题，他给我扔了这个他编的:

给定一个告诉您字符串是否有效的方法，编写一个接受字符串的方法，并返回最长的有效子字符串(不重新排序字符)。

我的第一个蛮力解决方案是找到输入字符串的所有子集，然后将它们插入(从最长到最短)给定的方法，直到找到有效的字符串并将其返回。

但这显然还不够好。

所以我试着这样想:

• 检查输入字符串

• 检查 inputString 的所有子集，其中 length == inputString length - 1

  <

• 以此类推，直到所有长度为1的子集都检查完毕，然后返回false

那么，我脑子里的问题是，为了使其成为最佳，我们希望利用我们只关心最长 有效字符串这一事实。如果我要递归地检查每个子集，那么当我真正寻找广度优先时，我会对子集进行深度优先遍历，所以我可以更快地找到最长的。

当我意识到这一点时，我陷入了困境。我什至无法想出伪代码来解决这个问题。

是否可以对字符串的子集进行“广度优先”搜索？

我能找到的最接近的解决方案是在 math stackexchange 上，有人发布了一个看起来很有前途的答案 -- https://math.stackexchange.com/questions/89419/algorithm-wanted-enumerate-all-subsets-of-a-set-in-order-of-increasing-sums

但不幸的是，我很难理解。

最好的解决方案是否只是对所有子集进行深度优先递归迭代并从那里返回最长的有效字符串？

Answer 1

string in

for int sub_len in len(in) , 1 //length of the substring must be smaller than/equal to
                               //the length of the input and atleast 1
    for int sub_offset in 0 , len(in) - sub_len
                               //the offset of the string must be in [0 , n]
                               //where n is the number of characters that are not in the
                               //substring
         string sub = substring(in , sub_offset , sub_len)

         if isValid(sub)
              return sub

这会为给定的输入(in)生成所有可能的子字符串，并返回第一个/最长的有效子字符串。