Why my code pass the separate test but not the whole test?


  • 0
    B

    Hi, the following is the code that I wrote (backtracking):

    public class StickerstoSpellWord {

    static int rst = Integer.MAX_VALUE;
    
    public int minStickers(String[] stickers, String target) {
        Set<Character> globSet = new HashSet<>();
        // this is pre processing
        for(String s : stickers){
            for(char c : s.toCharArray()){
                globSet.add(c);
            }
        }
        for(char c : target.toCharArray()){
            if(!globSet.contains(c)){
                return -1;
            }
        }
    
        // this is the main part
        Map<String, Map<Character, Integer>> countMap = constructMap(stickers);
        List<String> path = new ArrayList<>();
        backtracking(target, countMap, path, 0);
        return rst;
    }
    
    private void backtracking(String target, Map<String, Map<Character, Integer>> countMap, List<String> path, int count) {
        if(target.length() == 0){
            rst = Math.min(rst, count);
            return ;
        }
        for(String key : countMap.keySet()){
            if(path.contains(key)){
                continue;
            }
            path.add(key);
            String temp = new String(target);
            String combine = removeHelper(target, countMap, key);
            String newTarget = combine.split(" ")[0];
            int levelCount = Integer.parseInt(combine.split(" ")[1]);
            int nextCount = (levelCount == Integer.MAX_VALUE || count == Integer.MAX_VALUE) ? Integer.MAX_VALUE : levelCount + count;
            backtracking(newTarget, countMap, path, nextCount);
            path.remove(key);
            target = new String(temp);
        }
    
    }
    
    private String removeHelper(String target, Map<String, Map<Character, Integer>> countMap, String key){
        Map<Character, Integer> checkMap = new HashMap<>(countMap.get(key));
        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> tempMap = new HashMap<>(checkMap);
        int level = 0;
        while(checkContain(target, tempMap)){
            for(char c : target.toCharArray()){
                if(tempMap.containsKey(c)){
                    if(tempMap.get(c) == 1){
                        tempMap.remove(c);
                    }
                    else{
                        tempMap.put(c, tempMap.get(c) - 1);
                    }
                }
                else{
                    sb.append(c);
                }
            }
            tempMap = new HashMap<>(checkMap);
            target = sb.toString();
            sb = new StringBuilder();
            level++;
        }
        if(level != 0){
            return target + " " + level;
        }
        return target + " " + Integer.MAX_VALUE;
    }
    
    private boolean checkContain(String target, Map<Character, Integer> checkMap){
        for(char c : target.toCharArray()){
            if(checkMap.keySet().contains(c)){
                return true;
            }
        }
        return false;
    }
    
    private Map<String, Map<Character, Integer>> constructMap(String[] stickers){
        Map<String, Map<Character, Integer>> map = new HashMap<>();
        for(String s : stickers){
            if(!map.containsKey(s)){
                map.put(s, new HashMap<>());
            }
            for(char c : s.toCharArray()){
                Map<Character, Integer> currMap = map.get(s);
                if(currMap.containsKey(c)){
                    currMap.put(c, currMap.get(c) + 1);
                }
                else{
                    currMap.put(c, 1);
                }
            }
        }
        return map;
    }
    
    
    
    
    public static void main(String[] args){
        StickerstoSpellWord stickerstoSpellWord = new StickerstoSpellWord();
        String[] stickers = {"fly","me","charge","mind","bottom"};
        String target = "centorder";
        stickerstoSpellWord.minStickers(stickers, target);
        System.out.println(rst);
    }
    

    }

    It does not pass the test .But when I run locally and use the custom test, they all show the result of 4. Is there any suggestions for this or this is the bug of the system?

    The attachment is the screen shot.

    Any advice is appreciated

    0_1507672361708_Screen Shot 2017-10-10 at 2.48.10 PM.png


  • 1
    S

    using global will cause this kind of problem!


  • 0
    B

    @sguox002 thank you~!


Log in to reply
 

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