algorithm - coefficient - generate combinations leetcode




查找数字的字符串表示形式的所有可能的组合 (6)

给定一个映射:

A: 1
B: 2
C: 3
...
...
...
Z: 26

找出一个数字可以表示的所有可能的方式。 例如对于输入:“121”,我们可以表示为:

ABA [using: 1 2 1]
LA [using: 12 1]
AU [using: 1 21]

我试图考虑使用某种动态编程方法,但我不知道如何继续。 我在一次技术性的采访中被问到了这个问题。

这是我能想到的解决方案,请让我知道如果这看起来不错:

A[i]: Total number of ways to represent the sub-array number[0..i-1] using the integer to alphabet mapping.

解决方案[我错过了什么?]:

A[0] = 1 // there is only 1 way to represent the subarray consisting of only 1 number
for(i = 1:A.size):
    A[i] = A[i-1]
    if(input[i-1]*10 + input[i] < 26):
        A[i] += 1
    end
end
print A[A.size-1]

为了获得计数,动态编程方法非常简单:

A[0] = 1
for i = 1:n
  A[i] = 0
  if input[i-1] > 0                            // avoid 0
    A[i] += A[i-1];
  if i > 1 &&                          // avoid index-out-of-bounds on i = 1
      10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26
    A[i] += A[i-2];

如果你想列出所有的表示,动态编程并不是特别适合这个,你最好用一个简单的递归算法。


假设你只需要计算组合的数量。

假设0和后面的[1,9]中的整数不是有效的级联,那么强力策略将是:

Count(s,n)
    x=0
    if (s[n-1] is valid)
        x=Count(s,n-1)
    y=0
    if (s[n-2] concat s[n-1] is valid)
        y=Count(s,n-2)
    return x+y

更好的策略是使用分而治之:

Count(s,start,n)
    if (len is even)
    {
        //split s into equal left and right part, total count is left count multiply right count
        x=Count(s,start,n/2) + Count(s,start+n/2,n/2);
        y=0;
        if (s[start+len/2-1] concat s[start+len/2] is valid)
        {
            //if middle two charaters concatenation is valid
            //count left of the middle two characters
            //count right of the middle two characters
            //multiply the two counts and add to existing count
            y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1);
        }
        return x+y;
    }
    else
    {
        //there are three cases here:

        //case 1: if middle character is valid, 
        //then count everything to the left of the middle character, 
        //count everything to the right of the middle character,
        //multiply the two, assign to x
        x=...

        //case 2: if middle character concatenates the one to the left is valid, 
        //then count everything to the left of these two characters
        //count everything to the right of these two characters
        //multiply the two, assign to y
        y=...

        //case 3: if middle character concatenates the one to the right is valid, 
        //then count everything to the left of these two characters
        //count everything to the right of these two characters
        //multiply the two, assign to z
        z=...

        return x+y+z;
    }

蛮力解的时间复杂度为T(n)=T(n-1)+T(n-2)+O(1) ,它是指数的。

分治策略的时间复杂度为T(n)=3T(n/2)+O(1) ,即O(n ** lg3)。

希望这是正确的。


我认为,递归遍历所有可能的组合将做得很好:

mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G", 
"8":"H", "9":"I", "10":"J", 
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P", 
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W", 
"24":"A", "25":"Y", "26":"Z"}

def represent(A, B):
    if A == B == '':
        return [""]
    ret = []
    if A in mapping:
        ret += [mapping[A] + r for r in represent(B, '')]
    if len(A) > 1:
        ret += represent(A[:-1], A[-1]+B)
    return ret

print represent("121", "")

首先,我们需要找到一个直观的方式来列举所有的可能性。 我简单的构造,下面给出。

 let us assume a simple way to represent your integer in string format.

   a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1

现在,

我们需要找出在两个字符之间放置+号的可能性。 +在这里是指字符串联。

a1 - a2 - a3 - .... - an, - shows the places where '+' can be placed. So, number of positions is n - 1, where n is the string length. 

假设一个职位可能或不可能有一个+符号应表示为一个位。 所以,这可以归结为n-1的长度有多少个不同的位串,这显然是2 ^(n-1)。 现在为了列举可能性,通过每一个比特串,在各自的位置上放置正确的符号来获得每一个表示,

举个例子,121

   Four bit strings are possible 00 01 10 11
   1   2   1
   1   2 + 1
   1 + 2   1
   1 + 2 + 1

  And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation,

 x + y z a + b + c d

 would be (x+y) z (a+b+c) d  

希望能帮助到你。

当然,你将不得不照顾一些大于26的整数的边界情况。


这里是我在这里讨论的解决方案:

private static int decoder2(int[] input) {
    int[] A = new int[input.length + 1];
    A[0] = 1;

    for(int i=1; i<input.length+1; i++) {
      A[i] = 0;
      if(input[i-1] > 0) {
        A[i] += A[i-1];
      }
      if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) {
        A[i] += A[i-2];
      }
      System.out.println(A[i]);
    }
    return A[input.length];
}

这个问题可以用标准的DP算法在o(fib(n + 2))时间内完成。 我们有正确的n个子问题,并按钮,我们可以解决每个问题的大小我在o(fib(i))时间。 总结该系列给fib(n + 2)。

如果你仔细考虑这个问题,你会发现它是一个斐波那契数列。 我拿了一个标准的斐波那契代码,只是改变它,以适应我们的条件。

这个空间明显地与所有解决方案的大小相联系(fib(n))。

考虑这个伪代码:

Map<Integer, String> mapping = new HashMap<Integer, String>();

List<String > iterative_fib_sequence(string input) {
    int length = input.length;
    if (length <= 1) 
    {
        if (length==0)
        {
            return "";
        }
        else//input is a-j
        {
            return mapping.get(input);
        }
    }
    List<String> b = new List<String>();
    List<String> a = new List<String>(mapping.get(input.substring(0,0));
    List<String> c = new List<String>();

    for (int i = 1; i < length; ++i) 
    {
        int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (k-z)
        if (mapping.contains(dig2Prefix))
        {
            String word2Prefix = mapping.get(dig2Prefix);           
            foreach (String s in b)
            {
                c.Add(s.append(word2Prefix));
            }
        }

        int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (a-j)
        String word1Prefix = mapping.get(dig1Prefix);           
        foreach (String s in a)
        {
            c.Add(s.append(word1Prefix));
        }

        b = a;
        a = c;
        c = new List<String>();
    }
    return a;
}






combinations