leetcode2023-07-06

删除子文件夹

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        TrieNode root = new TrieNode();
        for (String fold : folder) {
            insert(root, fold);
        }
        List<String> ans = new ArrayList<>();
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();

        for (String fold : folder) {
            ans.add(fold);
            if (searchPrefix(root, fold) == -1) {
                set2.add(fold);
            }
        }
        // System.out.println(set2);
        ans.removeAll(set2);
        return ans;
    }

    //插入一个新单词
    public static void insert(TrieNode root,String str){
        if(root==null||str.length()==0){
            return;
        }
        char[] c=str.toCharArray();
        for(int i=0;i<str.length();i++){
            //如果该分支不存在，创建一个新节点
            if(root.nextNode.get(c[i])==null){
                root.nextNode.put(c[i], new TrieNode());
            }
            root=root.nextNode.get(c[i]);
            root.prefix++;//注意，应该加在后面
        }
        
        //以该节点结尾的单词数+1
        root.count++;
    }

    //查找该单词是否存在，如果存在返回数量，不存在返回-1
    public static int search(TrieNode root,String str){
        if(root==null||str.length()==0){
            return -1;
        }
        char[] c=str.toCharArray();
        for(int i=0;i<str.length();i++){
            //如果该分支不存在，表名该单词不存在
            if(root.nextNode.get(c[i])==null){
                return -1;
            }
            //如果存在，则继续向下遍历
            root=root.nextNode.get(c[i]);   
        }
        
        //如果count==0,也说明该单词不存在
        if(root.count==0){
            return -1;
        }
        return root.count;
    }
    
    //查询以str为前缀的单词数量
    public static int searchPrefix(TrieNode root,String str){
        if(root==null||str.length()==0){
            return -1;
        }
        char[] c=str.toCharArray();
        
        for(int i=0;i<str.length();i++){
            //如果该分支不存在，表名该单词不存在
            if(root.nextNode.get(c[i])==null){
                return -1;
            }
            if (root.nextNode.get(c[i]).count > 0 && (i + 1 < str.length() && c[i + 1] == '/' )) {
                return -1;
            }
            //如果存在，则继续向下遍历
            root=root.nextNode.get(c[i]);   
        }
        return 1;
    }


}

class TrieNode {
    int count;
    int prefix;
    Map<Character, TrieNode> nextNode=new HashMap<>();
    public TrieNode(){
        count=0;
        prefix=0;
    }
}