递归算法

Question

我刚开始写算法，我正在编写一个程序，检查一个字符串是否是其他两个字符串的有序混洗。(从左到右排序)例如

string 1 = dog
string 2 = cat
string shuffle = dcoagt

这是我的算法

**Algorithm: orderedSort(a,b,c)**
given strings a,b,c determine whether c is an ordered shuffle of a and b

l := length of (a + b)
if (l = 0) then
    return true
if (l not = length of c)
    return false
else
    d := substring of a position 1 to 1
    e := substring of b position 1 to 1
    f := substring of c position 1 to 1
if (d = f) then 
    return orderedSort(a-d, b, c-f) 
if (e = f) then
    return orderedSort(a, b-e, c-f)
if (d and e = f) then
    return orderedSort(a-d, b, c-f) or orderedSort(a, b-e, c-f)

我的问题是，这是正确的(如果不是，建议如何编写它)，因为我不确定如何为最后一条if语句编写伪代码，因为递归可以采用任何一种方式。

或者我不需要写最后一条if语句，程序员在编写程序时就会把它包括进来，这样它就不会在

string 1 = aa
string 2 = aaf
string combination = aafaa

我的Java实现是

public class OrderedSort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        String a = "xxyxxy";
        String b = "xxzxxz";
        String c = "xxzxxyxxyxxz";
        System.out.println(c + " is an ordered sort of " + a + " and " +  b + " ... " +  ordered(a,b,c));      
    }

    public static boolean ordered(String a, String b, String c){
        if(!((a.length()+b.length())==c.length()))
            return false;
        if(c.length()== 0)
            return true;
        if(a.length()>0 && b.length()>0 && a.substring(0,1).equals(b.substring(0,1)))
            return ordered(a.substring(1),b,c.substring(1)) || ordered(a,b.substring(1),c.substring(1));
        if(a.length()>0 && a.substring(0,1).equals(c.substring(0,1)))    
            return ordered(a.substring(1),b,c.substring(1));
        if(b.length()>0 &&b.substring(0,1).equals(c.substring(0,1)))
            return ordered(a,b.substring(1),c.substring(1));
        return false;
    }

}

Answer 1

你写的也是正确的，但是如果你写

return max( orderedSort(a-d, b, c-f), orderedSort(a, b-e, c-f))

这可以说得更清楚。

Answer 2

你的想法背后的逻辑是正确的，但不需要将子字符串传递给递归函数。通过为每个字符串保留一个指针，我们就可以完成任务。这是我的C++实现：

#include<iostream>
using namespace std;

string a = "aa";
string b = "aaf";
string c = "aafaa";

bool check( int p1, int p2, int p3 ){
    bool c1 = p1 < a.size();
    bool c2 = p2 < b.size();
    bool c3 = p3 < c.size();
    if ( !c1 && !c2 && !c3 ){
        return true;
    }
    if ( c1 && c2 && c3 && a[p1]==b[p2] && b[p2]==c[p3] ){
        bool b1 = check(p1+1,p2,p3+1);
        bool b2 = check(p1,p2+1,p3+1);
        return (b1 || b2);
    } else if ( c3 && c1 && a[p1] == c[p3] ) {
        return check(p1+1,p2,p3+1 );
    } else if ( c2 && c3 && b[p2] == c[p3] ) {
        return check(p1,p2+1,p3+1 );
    } else {
        return false;
    }
}


int main()
{
    cout << check(0,0,0) << endl;
}

Answer 3

这里有一些Ruby代码(它本身就是imho伪代码)。

# with two strings
s1, s2 = 'abc', 'defg'
s1.split('').shuffle.join + s2.split('').shuffle.join
# "cbagefd"

# with variable number of strings
%w[abc defg hijkl].map{|string| string.split('').shuffle.join}.join
# "bacefdghlijk"

不需要递归，您可以对每个字符串本身进行混洗，并将它们连接(连接)在一起。

代码的一些解释：

.split(''): splits the string in an array of characters
.shuffle and .join speak for them self
%w[...] spilts the contained string in array of strings separated by a space
.map makes an array of the contained block of code