想了很久,可还是做不出!题目如下:
给定一组字符串,要求求出一个最短的字符串使得它包含所有给出的字符串。
比如"a","bc","ca".输出应该是"bca".
为不至进入迷区,再举过例子:cabe", "bef", "abex",这三个字串中,输出结果应该是:cabexbef.为了更好地让大家明白再举例子:如("acb","acbbc","ef"),应输出"acbbcef"
                             ("bbf","fbb","acbb"),应输出"acbbfbb"而不是"fbbfacbb"
                           ("abc","def","hij"),应输出"abcdefhij"<注意了,是最短的字串>
           
速度至上,代码的可读性也要好,附上适当的注释!能用正则表达式吗?如能,要怎样做?

解决方案 »

  1.   

    给你个思路吧,也不难的
    用Dictionary对象,用mid把每个字符串的字符存入Dictionary,存入时用exist属性判断是否存在,存在的话就不添加,否则add,然后For i = 0 To Dictionary.Count -1,把所有的对象连起来就可以了
      

  2.   

    测试了全排列,第一个还可以("a","bc","ca".输出应该是"bca". )第二个20分钟都没有出结果(cabe", "bef", "abex",这三个字串中,输出结果应该是:cabexbef.)看来简单的全排列是不行的
    以下是全排列程序,仅供参考:Dim iStr(), ii As LongPrivate Sub Command1_Click()
        Dim a(), b, c, i, d
        Dim in1, in2, in3
        in1 = "a": in2 = "bc": in3 = "ca"       '比如"a","bc","ca".输出应该是"bca".
        'in1 = "cabe": in2 = "bef": in3 = "abex"  'cabe", "bef", "abex",这三个字串中,输出结果应该是:cabexbef.
        
        b = in1 & in2 & in3
        
        c = Len(b) - 1
        ReDim a(c)
        For i = 0 To c
            a(i) = Mid(b, i + 1, 1)
        Next
        pai a, 0, c + 1
                
        For j = 1 To Len(b)
            For i = 0 To UBound(iStr)
                If InStr(iStr(i), in1) <> 0 And InStr(iStr(i), in2) <> 0 And InStr(iStr(i), in3) <> 0 Then
                   d = Mid(iStr(i), 1, j)
                   If InStr(d, in1) <> 0 And InStr(d, in2) <> 0 And InStr(d, in3) <> 0 Then
                       Debug.Print d
                       Exit Sub
                    End If
                End If
           Next
       Next
            
            
    End SubSub chang(a(), m As Integer)
       Dim i As Integer, j As Integer
       Dim temp As String
       temp = a(0)
       For i = 0 To m - 1
           a(i) = a(i + 1)
       Next
       a(i) = temp
    End SubSub pai(a(), m As Integer, n As Integer)
        Dim k As Integer
        If m < n Then
           For k = 0 To m
               pai a, m + 1, n
               chang a, m
           Next
        Else
           ReDim Preserve iStr(ii)
           iStr(ii) = Join(a, "")
           ii = ii + 1
           DoEvents
        End If
       
    End Sub
      

  3.   

    Private Sub Form_Load()
    Dim s As String, sTmp As String, sLeft As String, sRight As String, sLong As String
    Dim sStrIn() As String
    Dim i As Byte, l As Byte
    's = "acb,acbbc,ef,b,cbb"
    s = "bbf,fbb,acbb"
    's = "a,bc,ca"
    sStrIn = Split(s, ",")                              '赋值给数组
    For i = 0 To UBound(sStrIn)                         '排序
        For l = i To UBound(sStrIn)
            If Len(sStrIn(i)) < Len(sStrIn(l)) Then
                sTmp = sStrIn(i)
                sStrIn(i) = sStrIn(l)
                sStrIn(l) = sTmp
            End If
        Next l
    'Debug.Print sStrIn(i)
    Next isLong = sStrIn(0) '最长的赋值给母串
    sLeft = sStrIn(0)
    sRight = sStrIn(0)
    For i = 1 To UBound(sStrIn) '把不包含的字符加到左边
        If InStr(sLeft, sStrIn(i)) = 0 Then
            For l = 1 To Len(sStrIn(i))
                If InStr(Left(sLeft, Len(sStrIn(i)) - l), Right(sStrIn(i), l)) Then
                    sLeft = Left(sStrIn(i), Len(sStrIn(i)) - l) & sLeft
                End If
            If l = Len(sStrIn(i)) Then sLeft = sStrIn(i) & sLeft
            Next l
        End If
    Next iFor i = 1 To UBound(sStrIn) '把不包含的字符加到右边
        If InStr(sRight, sStrIn(i)) = 0 Then
            For l = 1 To Len(sStrIn(i))
                If InStr(Right(sRight, Len(sStrIn(i)) - l), Left(sStrIn(i), l)) Then
                    sRight = Right(sStrIn(i), Len(sStrIn(i)) - l) & sRight
                End If
            If l = Len(sStrIn(i)) Then sRight = sRight & sStrIn(i)
            Next l
        End If
    Next i
    If Len(sRight) < Len(sLeft) Then sLong = sRight Else sLong = sLeft '取最短的
    Debug.Print "L:" & sLeft & "  R:" & sRight & "最终:" & sLong
    End Sub这个代码能正确实现你例程里的字符串。但是估计有其他特殊情况,请测试。
      

  4.   

    呐,我又想了想,似乎每取一个(i+1)就做次sLeft和sRight长度判断更合理。
      

  5.   

    http://download.csdn.net/source/1951661
    一本全面彻底讲解字符串查找算法的书。 书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有进一步的参考文献。 一本研究字符串查找算法不容错过的好书。 
      

  6.   

    Option ExplicitPrivate Sub Form_Load()
        Dim col As New Collection
        Call col.Add("a")
        Call col.Add("bc")
        Call col.Add("ca")
        Debug.Print FindMinCouple(col)
        
        Call clear(col)
        Call col.Add("cabe")
        Call col.Add("bef")
        Call col.Add("abex")
        Debug.Print FindMinCouple(col)    Call clear(col)
        Call col.Add("acb")
        Call col.Add("acbbc")
        Call col.Add("ef")
        Debug.Print FindMinCouple(col)    Call clear(col)
        Call col.Add("bbf")
        Call col.Add("fbb")
        Call col.Add("acbb")
        Debug.Print FindMinCouple(col)    Call clear(col)
        Call col.Add("abc")
        Call col.Add("def")
        Call col.Add("hij")
        Debug.Print FindMinCouple(col)
    End SubPrivate Sub clear(ByVal col As Collection)
        Dim i As Long
        For i = 1 To col.Count
            Call col.Remove(1)
        Next
    End Sub
    '---------------------------------------------------------------------------------------
    ' 过程名称: FindMinCouple
    ' 过程作者: sonic_andy
    ' 创建日期: 2010/1/24
    ' 实现功能: 获取最小长度的组合字符串
    ' 参数 col: 源串集合
    ' 返回值: 得到的最小组合
    '---------------------------------------------------------------------------------------
    Private Function FindMinCouple(ByRef col As Collection) As String
        ' 获取直接拼接的字符串
        Dim i As Long
        For i = 1 To col.Count
            FindMinCouple = FindMinCouple & col(i)
        Next
        Call Combine(col, 2, col(1), FindMinCouple)
    End Function'---------------------------------------------------------------------------------------
    ' 过程名称: Combine
    ' 过程作者: sonic_andy
    ' 创建日期: 2010/1/24
    ' 实现功能: 递归组合所有可能的情况
    ' 参数 colSrc: 源串集合
    ' 参数 lngDepth: 递归深度
    ' 参数 strCombined: 上一步组合好的字符串
    ' 参数 strResult: 最短字符串
    '---------------------------------------------------------------------------------------
    Private Sub Combine(ByRef colSrc As Collection, _
                        ByVal lngDepth As Long, _
                        ByVal strCombined As String, _
                        ByRef strResult As String)
        ' 如果已经组合了所有源串,则开始比较结果
        If lngDepth > colSrc.Count Then
            If Len(strCombined) < Len(strResult) Then
                strResult = strCombined
            End If
            Exit Sub
        End If
        
        ' 本次需要被加入的字符串
        Dim strCurrent As String
        strCurrent = colSrc(lngDepth)
        
        ' B=strCombined
        ' A=strCurrent
        
        ' BAB包含
        Dim lngPos As Long
        lngPos = InStr(1, strCombined, strCurrent)
        If lngPos > 0 Then
            Call Combine(colSrc, lngDepth + 1, strCombined, strResult)
        End If
        
        ' ABA包含
        lngPos = InStr(1, strCurrent, strCombined)
        If lngPos > 0 Then
            Call Combine(colSrc, lngDepth + 1, strCurrent, strResult)
        End If
        
        Dim lngCurrentLength As Long
        lngCurrentLength = Len(strCurrent)
        
        Dim lngCombinedLength As Long
        lngCombinedLength = Len(strCombined)
        
        Dim lngMinLength As Long
        If lngCombinedLength < lngCurrentLength Then
            lngMinLength = lngCombinedLength
        Else
            lngMinLength = lngCurrentLength
        End If
        
        Dim i As Long
        For i = 1 To lngMinLength - 1
            ' AB重合
            If Right(strCurrent, i) = Left(strCombined, i) Then
                Call Combine(colSrc, _
                             lngDepth + 1, _
                             strCurrent & Right(strCombined, lngCombinedLength - i), _
                             strResult)
            End If
            
            ' BA重合
            If Right(strCombined, i) = Left(strCurrent, i) Then
                Call Combine(colSrc, _
                             lngDepth + 1, _
                             strCombined & Right(strCurrent, lngCurrentLength - i), _
                             strResult)
            End If
        Next
        
        ' 不重合
        Call Combine(colSrc, lngDepth + 1, strCurrent & strCombined, strResult)
        Call Combine(colSrc, lngDepth + 1, strCombined & strCurrent, strResult)
    End Sub
      

  7.   

    还可以优化一下,遍历过程中,如果strCombined串长度已经超过strResult的长度,可以直接返回.
      

  8.   

    这是优化后的
    '---------------------------------------------------------------------------------------
    ' 过程名称: Combine
    ' 过程作者: sonic_andy
    ' 创建日期: 2010/1/24
    ' 实现功能: 递归组合所有可能的情况
    ' 参数 colSrc: 源串集合
    ' 参数 lngDepth: 递归深度
    ' 参数 strCombined: 上一步组合好的字符串
    ' 参数 strResult: 最短字符串
    '---------------------------------------------------------------------------------------
    Private Sub Combine(ByRef colSrc As Collection, _
                        ByVal lngDepth As Long, _
                        ByVal strCombined As String, _
                        ByRef strResult As String)
        If Len(strCombined) >= Len(strResult) Then
            Exit Sub
        End If    ' 如果已经组合了所有源串,则开始比较结果
        If lngDepth > colSrc.Count Then
            strResult = strCombined
            Exit Sub
        End If
        
        ' 本次需要被加入的字符串
        Dim strCurrent As String
        strCurrent = colSrc(lngDepth)
        
        ' B=strCombined
        ' A=strCurrent
        
        ' BAB包含
        Dim lngPos As Long
        lngPos = InStr(1, strCombined, strCurrent)
        If lngPos > 0 Then
            Call Combine(colSrc, lngDepth + 1, strCombined, strResult)
        End If
        
        ' ABA包含
        lngPos = InStr(1, strCurrent, strCombined)
        If lngPos > 0 Then
            Call Combine(colSrc, lngDepth + 1, strCurrent, strResult)
        End If
        
        Dim lngCurrentLength As Long
        lngCurrentLength = Len(strCurrent)
        
        Dim lngCombinedLength As Long
        lngCombinedLength = Len(strCombined)
        
        Dim lngMinLength As Long
        If lngCombinedLength < lngCurrentLength Then
            lngMinLength = lngCombinedLength
        Else
            lngMinLength = lngCurrentLength
        End If
        
        Dim i As Long
        For i = 1 To lngMinLength - 1
            ' AB重合
            If Right(strCurrent, i) = Left(strCombined, i) Then
                Call Combine(colSrc, _
                             lngDepth + 1, _
                             strCurrent & Right(strCombined, lngCombinedLength - i), _
                             strResult)
            End If
            
            ' BA重合
            If Right(strCombined, i) = Left(strCurrent, i) Then
                Call Combine(colSrc, _
                             lngDepth + 1, _
                             strCombined & Right(strCurrent, lngCurrentLength - i), _
                             strResult)
            End If
        Next
        
        ' 不重合
        Call Combine(colSrc, lngDepth + 1, strCurrent & strCombined, strResult)
        Call Combine(colSrc, lngDepth + 1, strCombined & strCurrent, strResult)
    End Sub
      

  9.   


    似乎可以这样解:假设你有 n 个需要合并的元素,我们称之为 n 元问题。n > 1。第一步:简单降元。首先取最长的一个(称为母元素),循环遍历其他 n - 1 个元素(成为子元素),看是否有任意一个子元素完整包含于母元素。用 InStr 即可。如果找到这样的子元素,即消除该子元素,当作 n - 1 元问题来处理(n = n - 1)。如果 n 已经等于 1,则已经得解。否则仍从简单降元开始处理。第二步:
    从最短的子元素开始遍历,将其前导和后缀于母元素,得到一个更长的串。分别遍历剩余的子元素,看是否包含。注意,不要找到一个包含子元素就跳出。要记录被包含的元素,及其总长度。结果分四种情况:1 仅前导或后缀得到包含,则该长串是新的母元素,消除被包含者。
    2 如果前导和后缀均得到包含,比较包含总长度,取其长者。如前处理。
    3 没有包含。则测试下一个子元素与母元素合并。直至全部遍历,如果没有包含,将剩余子元素与母元素全部合并,顺序无关。此解法不一定能得到最佳解,但得到较优解是没有问题的。
      

  10.   

    可以将所有字符串两两关系构成有向图中的路径,长度就是首尾重复字符数(取负值,可以统一加上一个定值变成正数),以 "cabe", "bef", "abex" 为例:
    cabe -> bef : -2
    bef -> cabe : 0
    cabe -> abex : -3
    abex -> cabe : 0
    bef -> abex : 0
    abex -> bef : 0
    然后问题就变成了在有向图中找一条经过所有节点并且每个节点只经过一次的最短路径,这是个讨论得非常多的典型算法问题了。
      

  11.   

    打靶来解决嘛.26个字母,开一个数组
    S(25),0是A,依次表示26个字母.
    如果有A字母,S(0)=1
    最后把值是1的拼接起来就OK了.