贴纸拼词
难度：简单
困难题先cv
代码如下：
public int minStickers(String[] stickers, String target) {
char c[]=target.toCharArray();
Arrays.sort(c);//使得字母的位置集中靠左并排序
int idxRange[][]=new int[26][];//记录排序后每一种字母的下标范围，字母不存在则置为-1
for(int i=0;i<26;i++){idxRange[i]=new int[]{-1,-1};}
int left=0;
//以下处理每个字母集中后的下标区间：
for(int i=1;i<c.length;i++){
if(c[i]!=c[i-1]){
idxRange[c[i-1]-'a']=new int[]{left,i-1};//代表这个字母的最左和最右的坐标
left=i;
}
}
idxRange[c[c.length-1]-'a']=new int[]{left,c.length-1};
int count[][]=new int[stickers.length][26];//预处理每个sticker的字母频次
for(int i=0;i<stickers.length;i++){for(char ch:stickers[i].toCharArray()){count[i][ch-'a']++;}}
int ans[]=new int[1<<c.length];
Arrays.fill(ans,1000);
ans[0]=0;
for(int i=1;i<ans.length;i++){
if(!isLegalMask(i,idxRange)){continue;}//非法mask需要剪枝
for(int j=0;j<stickers.length;j++){
int mask=i;
for(int k=0;k<26;k++){
if(count[j][k]==0||idxRange[k][0]==-1){continue;}
int mostRight=idxRange[k][1];//寻找字母最右边的1；
while(mostRight>=idxRange[k][0]&&(i&(1<<mostRight))==0){mostRight--;}
//此时区间1的范围是闭区间[idxRange[k][0],mostRight]
for(int p=0;p<=mostRight-idxRange[k][0]&&p<count[j][k];p++){mask-=(1<<(mostRight-p));}
}
ans[i]=Math.min(ans[i],1+ans[mask]);
}
}
return ans[ans.length-1]>=1000?-1:ans[ans.length-1];
}
public boolean isLegalMask(int mask,int idxRange[][]){
//判断是否是字母靠左的合法mask
for(int i=0;i<26;i++){
if(idxRange[i][0]==-1){continue;}
for(int j=idxRange[i][1];j>=idxRange[i][0];j--){
if((mask&(1<<j))!=0){
//在范围内的遇到1后如果再次遇到0，那么这个mask是非法的
for(int k=j-1;k>=idxRange[i][0];k--){if((mask&(1<<k))==0){return false;}}
break;
}
}
}
return true;
}
执行结果：成功
