Easy java solution beats 98% of submissions with explanation


  • 0
    D

    In this solution, we will be using a HashMap , to store the file content and the complete path of the files which has the corresponding content in an Arraylist as key, value pairs.
    <fileContent,ArrayList<path of files which have fileContent>>

    Step 1: When we first iterate through the array paths, we split the entries based on " " and store it in an array currentDirectory; we know that the first entry will be the file path and the following entries will be the file names along with their contents

    Step 2:We iterate through the file names and contents which is present in currentDirectory, and keep track of index of "(" and ")".

    Step 3: The file content is the substring between "(" and ")" and file name is the substring from the start of the string to "(".

    Step 4: We check to see if the file content is already present in the map,
    if present, add the path of the current file to list corresponding to the fileContent
    if not, add a new (fileContent,filePath) entry to the map.

    Step 5: At the end, as we only want the file paths if 2 or more files have the same content, we check to see if ArrayList present in value field of the map has a size greater than 1 and if it does we add it to the solution.

    public class Solution {
        public List<List<String>> findDuplicate(String[] paths) {
            
            //variable to store answer
            List<List<String>> solution=new ArrayList<List<String>>();
            
            //Base case: if paths array is null or length 0, return solution
            if(paths==null || paths.length==0)
                return solution;
            
            //General case: if paths array has 1 or more contents
            //hashmap to store file content and file paths as key,value pairs
            HashMap<String,List<String>> map=new HashMap<String,List<String>>();
            
            //for loop to iterate through paths array
            for(int i=0;i<paths.length;i++)
            {
                /*store the name of the directory as well as the 
                different files present in that same directory with their contents*/
                String[] currentDirectory=paths[i].split(" ");
                
                //first index will be the path of the directory
                String directoryName=currentDirectory[0];
                
                //iterate through different files present in the current directory
                for(int j=1;j<currentDirectory.length;j++)
                {
                    
                    int openIndex=currentDirectory[j].indexOf("(");
                    
                    int closeIndex=currentDirectory[j].indexOf(")");
                    
                    
                    //store the file content and name of the file
                    String fileContent=currentDirectory[j].substring(openIndex+1,closeIndex);
                    
                    String fileName=currentDirectory[j].substring(0,openIndex);
                    
                    /*if map contains file content, add file path to the the list
                    else add new map entry*/
                    if(map.containsKey(fileContent))
                    {
                        List<String> list=map.get(fileContent);
                        list.add(directoryName+"/"+fileName);
                        map.put(fileContent,list);
                        
                    }
                    else
                    {
                        List<String> list=new ArrayList<String>();
                        list.add(directoryName+"/"+fileName);
                        map.put(fileContent,list);
                    }
                    
                }
            }
            
            /*iterate through the file content(keys in the map) and get 
            corresponding directories of the files with that content*/
            Set keys=map.keySet();
            Iterator it=keys.iterator();
            Object key;
            List<String> value=new ArrayList<String>();
            
            while(it.hasNext())
            {
                key=it.next();
                value=map.get(key);
                
                //add the directories to the solution only when 2 or more files have the same content
                if(value.size()>1)
                    solution.add(value);
            }
            
            return solution;
        }
    }
    

Log in to reply
 

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