BFS with Bit(16 base)


  • 0
    T
    public class Solution {
        public int MinStickers(string[] stickers, string target) {
            var mapping = new Dictionary<char,int>();
            var m2 = new Dictionary<int,char>();
            var countMapping = new int[26];
            long targetNumber = 0;
            foreach(var c in target){
                if(!mapping.ContainsKey(c)){
                    int count = mapping.Count();
                    mapping.Add(c,count);
                    m2.Add(count,c);
                }
                targetNumber += (long)Math.Pow(16,mapping[c]);
                countMapping[c-'a']++;
            }
            //Console.WriteLine(string.Join(" , ",mapping.Select(x=>"("+x.Key+","+x.Value+")")));
            //Console.WriteLine(string.Join(" , ",m2.Select(x=>"("+x.Key+","+x.Value+")")));
            var list = new List<long>();
            var visitedChar = new HashSet<char>();
            foreach(var w in stickers){
                long num = 0;
                var m = new int[26];
                foreach(var c in w){
                    if(mapping.ContainsKey(c) && ++m[c-'a'] <= countMapping[c-'a']){
                        num += (long)Math.Pow(16,mapping[c]);
                        visitedChar.Add(c);
                    }
                }
                if(num != 0){
                    list.Add(num);
                }
            }
            if(visitedChar.Count < mapping.Count())
                return -1;
            
            var possible = new HashSet<long>();
            possible.Add(0);
            int result = 1;
            var visited = new HashSet<long>();
            while(possible.Any()){
                var newp = new HashSet<long>();
                foreach(var item in possible){
                    foreach(var p in list){
                        long N = item;
                        long M = p;
                        long newR = 0;
                        int index = 0;
                        while(N>0||M>0){
                            //Console.WriteLine(index);
                            newR += (long)(Math.Min(countMapping[m2[index]-'a'],N%16+M%16) * Math.Pow(16,index));
                            N/=16;
                            M/=16;
                            index++;
                        }
                        //Console.WriteLine(item+","+p+","+newR);
                        if(newR>=targetNumber)
                            return result;
                        if(visited.Add(newR)){
                            newp.Add(newR);
                        }
                    }
                }
                result++;
                //Console.WriteLine(newp.Count);
                possible = newp;
            }
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.