字母从数字没有分隔符

Question

如果我们有我们的“1125”，最大值为例如输入，那么我们的输出是：

[ [1,1,2,5] , [11,2,5] , [1,12,5] , [1,1,25] , [11,25] ]

这是一个由数组以各种可能的方式将字符分隔为小于值。

我们可以使用它来解密已经将字母转换为字母数字但没有分隔符的消息。

这里是我当前的代码这是我第一次尝试解决这个问题：

Array.prototype.indexOfArray=function(array){ 
    for(var i=0;i<this.length;i++){ 
     if(this[i].length==array.length){ 
      var same=true; 
      for(var j=0;j<this[i].length;j++){ 
       if(this[i][j]!=array[j]){ 
        same=false; 
        break; 
       } 
      } 
      if(same){ 
       return i; 
      } 
     } 
    } 
    return-1; 
}; 
function possibilities(string,max){ //The function I'm talking about. 
    var output=[]; 
    (function collector(array,held,start){ 
     for(var i=start;i<string.length;i++){ 
      var char=string[i]; 
      if(Number(held+char)>max){ 
       array.push(held); 
       held=char; 
      }else{ 
       held+=char; 
       if(i!=string.length-1){ 
        collector(array.slice().concat(held),"",i+1); 
       } 
      } 
     } 
     if(held.length>0){ 
      array.push(held); 
     } 
     if(output.indexOfArray(array)==-1){ 
      output.push(array); 
     } 
    })([],"",0); 
    return output; 
} 
var message="302213"; //"dawn" is "3 0 22 13" with delimiters 
var alphabet="abcdefghijklmnopqrstuvwxyz"; 
var solutions=possibilities(message,alphabet.length); 
for(var i=0;i<solutions.length;i++){ 
    console.log(solutions[i].join(",")+" : "+solutions[i].map(x=>alphabet[Number(x)]).join("")); 
} 

，并打印出：

3,0,2,2,1,3 : daccbd 
3,0,2,2,13 : daccn 
3,0,2,21,3 : dacvd 
3,0,22,1,3 : dawbd 
3,0,22,13 : dawn 
3,02,2,1,3 : dccbd 
3,02,2,13 : dccn 
3,02,21,3 : dcvd 
3,022,1,3 : dwbd 
3,022,13 : dwn 

我怎么能提高呢？这个算法的名字是什么？

Answer 1

您可以使用不同的接合方法将零件粘合在一起，其中2 ^{array.length - 1}作为不同分块零件的形式。然后过滤出那些，其具有大于25

function split(string) { 
 
    var array = string.split(''), 
 
     result = [], 
 
     i, l = 1 << (array.length - 1), 
 
     v, j, 
 
     temp; 
 

 
    for (i = 0; i < l; i++) { 
 
     v = i; 
 
     temp = [array[0]]; 
 
     for (j = 1; j < array.length; j++) { 
 
      if (v & 1) { 
 
       temp[temp.length - 1] += array[j]; 
 
      } else { 
 
       temp.push(array[j]); 
 
      } 
 
      v = v >> 1; 
 
     } 
 
     result.push(temp); 
 
    } 
 
    return result.filter(function (a) { 
 
     return a.every(function (b) { 
 
      return b < 26; 
 
     }); 
 
    }); 
 
} 
 

 
function output(array) { 
 
    array.forEach(function (a) { 
 
     console.log(a.join(), a.map(function (b) { return (+b + 10).toString(36); }).join('')); 
 
    }); 
 
} 
 

 
output(split('302213')); 
 
output(split('1125'));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

这是递归方法很好的例子的值。让我们做一些定义，先

1. 输入

   输入小写的字符串，<'a','z'>编码为<1,26>无定界符。

2. 输出

   我们想要获得字符串的组合的所有解码每个有效解码1对2位代码。

3. 启发式

   所以2个代码可以用{ 1,2 }就{ 0 }意味着我们韩德林2位代码{ 10,20 }或{ 0 }为<0,25>这可以用来降低组合数。

递归算法

如果我们有像decode(in);一些函数，那么我们可以递归地做到这一点简单的方式是这样的：

decode (string in) 
{ 
l=in.Length(); 
add_combination(tochar(in[1]) + in.substring(2,l-1)); 
add_combination(tochar(10*in[1]+in[2]) + in.substring(3,l-2)); 
} 

在平原的话需要先1或2位字符并解码字符串的其余部分。让我们假设你的例子1125的递归会像这样：

||decode(1125)| 
|1|decode(125)| 
    |1,1|decode(25)| 
    |1,1,2|decode(5)| 
    |1,1,2,5|decode()| - combination 
    |1,1,25|decode()| - combination 
    |1,12|decode(5)| 
    |1,12,5|decode()| - combination 
|11|decode(25)| 
    |11,2|decode(5)| 
    |11,2,5|decode()| - combination 
    |11,25|decode()| - combination 

的intendation代表递归层，第一部分是当前组合的前缀（in0）和右部分字符串的其余部分进行解码（in1+i）。

这听起来很简单，但要编码这种反馈有点复杂。那是因为我们需要记住一个解决方案而不是一个解决方案。我决定将所有结果存储在由\r\l行结尾分隔的单个字符串中。这里工作VCL/C++例如：

//--------------------------------------------------------------------------- 
AnsiString txt_encode0(const AnsiString &in) // <'a','z'> -> <0,25> 
    { 
    int i,l=in.Length(); 
    AnsiString txt=""; 
    for (i=1;i<=l;i++) txt+=int(in[i]-'a'); 
    return txt; 
    } 
//--------------------------------------------------------------------------- 
AnsiString txt_encode1(const AnsiString &in) // <'a','z'> -> <1,26> 
    { 
    int i,l=in.Length(); 
    AnsiString txt=""; 
    for (i=1;i<=l;i++) txt+=int(in[i]-'a'+1); 
    return txt; 
    } 
//--------------------------------------------------------------------------- 
void txt_decode0(AnsiString &out,AnsiString in0,const AnsiString &in1,int i,int &l) // recursion <0,25> -> <'a','z'> 
    { 
    // stop recursion if whole string processed 
    if (i>l) { out+=in0+"\r\n"; return; } 
    int a0,a1; 
    // load first 2 digits from i if second digit is not applicable set is as -1 
       a0=in1[i]-'0'; i++; 
    if (i<= l) a1=in1[i]-'0'; else a1=-1; 
    if (a0> 2) a1=-1; // >2 means always 1 digit code 
    if (a0==0) a1=-1; // =0 means always 1 digit code 
    // one digit combination 
    in0+=char(a0+'a'); 
    txt_decode0(out,in0,in1,i,l); 
    in0.SetLength(in0.Length()-1); 
    // 2 digit combination 
    if (a1>=0) 
     { 
     a0*=10; 
     a0+=a1; i++; 
     if (a0<=26) 
      { 
      in0+=char(a0+'a'); 
      txt_decode0(out,in0,in1,i,l); 
      } 
     } 
    } 
AnsiString txt_decode0(const AnsiString &in) // <0,25> -> <'a','z'> 
    { 
    int l=in.Length(); 
    AnsiString in0="",out=""; 
    txt_decode0(out,in0,in,1,l); 
    return out; 
    } 
//--------------------------------------------------------------------------- 
void txt_decode1(AnsiString &out,AnsiString in0,const AnsiString &in1,int i,int &l) // recursion <1,26> -> <'a','z'> 
    { 
    // stop recursion if whole string processed 
    if (i>l) { out+=in0+"\r\n"; return; } 
    int a0,a1; 
    // load first 2 digits from i if second digit is not applicable set is as -1 
       a0=in1[i]-'0'; i++; 
    if (i<=l) a1=in1[i]-'0'; else a1=-1; 
    if (a0> 2) a1=-1; // >2 means always 1 digit code 
    // one digit combination 
    if (a1!=0)   // =0 means always 2 digit code 
     { 
     in0+=char(a0+'a'-1); 
     txt_decode1(out,in0,in1,i,l); 
     in0.SetLength(in0.Length()-1); 
     } 
    // 2 digit combination 
    if (a1>=0) 
     { 
     a0*=10; 
     a0+=a1; i++; 
     if (a0<=26) 
      { 
      in0+=char(a0+'a'-1); 
      txt_decode1(out,in0,in1,i,l); 
      } 
     } 
    } 
AnsiString txt_decode1(const AnsiString &in) // <1,26> -> <'a','z'> 
    { 
    int l=in.Length(); 
    AnsiString in0="",out=""; 
    txt_decode1(out,in0,in,1,l); 
    return out; 
    } 
//--------------------------------------------------------------------------- 
void main() 
    { 
    AnsiString enc,dec,txt; 
    txt="decoding"; 
    enc=txt_encode0(txt); 
// enc="302213"; 
    dec=txt_decode0(enc); 
    } 
//--------------------------------------------------------------------------- 

的txt_encode0,txt_decode0运行在<0,25>和txt_encode1,txt_decode1上<1,26>范围内工作。

out正在保存有效组合列表。 in0包含组合的实际前缀in1保存输入字符串。 i是in1和l的实际组合的起始索引，长度为in1。在这里，输出<0,25>：

message:decoding 
encoded:3421438136 
decoded in [ 0.013 ms] 

decbedibdg 
decbeding 
decodibdg 
decoding 
devedibdg 
deveding 

和您的样本：

encoded:302213 
decoded in [ 0.007 ms] 

daccbd 
daccn 
dacvd 
dawbd 
dawn 

我使用AnsiString从VCL他们从自身分配1与索引动态字符串。例如AnsiString s="abc";s[1]=='a'它的大小是s.Length()所以s[s.Length()]=='c'。

Answer 3

下面是JavaScript中的递归方法。这个想法是，如果字符串中接下来的两个字符可以用两种方式解释，那么将两种方式中的每一种添加到每个结果中以分割字符串的下一部分。否则，只需在每个结果中添加第一个字符以分割字符串的下一部分。

function possibilities(str){ 
 
    if (str.length === 0) return [[]]; 
 
    
 
    var result = [], next = possibilities(str.substr(1)); 
 
     
 
    for (var i=0; i<next.length; i++) 
 
    result.push([str[0]].concat(next[i])); 
 

 
    if (str.length > 1 && str[0] !== '0' && str.substr(0,2) < 27){ 
 
    next = possibilities(str.substr(2)); 
 
     
 
    for (var i=0; i<next.length; i++) 
 
     result.push([str.substr(0,2)].concat(next[i])); 
 
    } 
 
    
 
    return result; 
 
} 
 

 
console.log(possibilities('1125')); 
 
console.log(possibilities('302213'));