22~24ms JAVA solution using insert sorting to maintain inner List order


  • 0
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans =new ArrayList<List<String>>();
        HashMap<String,Integer> hm=new HashMap<String,Integer>();
        
    	for(int i=0;i<strs.length;i++)
    	{
    		boolean added=false;
    		char[] tc=strs[i].toCharArray();
    		Arrays.sort(tc);
    		String tag=new String(tc);
    		if(hm.containsKey(tag))
    		{
    			List<String> tl=ans.get(hm.get(tag));
    			tl.add(strs[i]);
    			oneinsert(tl);
    			added=true;
    		}	
    		if(added==false)
    		{
    			List<String> tmp=new ArrayList<String>();
    			tmp.add(strs[i]);
    			ans.add(tmp);
    			hm.put(new String(tc),ans.size()-1);
    		}
    	}
    	return ans;
    }
    
    public void oneinsert(List<String> tl)
        {
        	int i=tl.size()-1;
        	String end=tl.get(i);
        	
        	String before=tl.get(i-1);
        	if(end.length()==0) return;
        	while(stringorder(end,before))
        	{
        		String tmp=before;
        		tl.set(i-1, end);
        		tl.set(i, tmp);
        		i--;
        		if(i==0) break;
        		end=tl.get(i);
        		before=tl.get(i-1);
        	}
        }
    public boolean stringorder(String a,String b)
        {
        	
        	int l1=a.length();
        	int l2=b.length();
        	int i=0;
        	int count=0;
        	while(i<l1&&i<l2)
        	{
        		if(a.charAt(i)-b.charAt(i)>0) return false;
        		if(a.charAt(i)-b.charAt(i)<0) return true;
        		if(a.charAt(i)-b.charAt(i)==0) count++;
        		i++;
        	}
        	if(l1<l2&&i==count) return true; 
        	return false;
        }

Log in to reply
 

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