The most efficient Java solution till now, no extra space


  • 0
    M

    My idea is focus on shift essence. Loop through the String Array, check if curent element strings[i] is shfited by existed sequence:
    (1) if it is, add strings[i] to the sequence;
    (2) if it isn't, create a new sequence.

    public List<List<String>> groupStrings(String[] strings) {
        Arrays.sort(strings);
    
        List<List<String>> LL = new ArrayList();
        for (String s : strings){
    	    boolean isOld = false;
    	    for (List<String> L : LL){
    		    if (L.size() > 0 && isAligned(L.get(0), s)) {
    			L.add(s);
    			isOld = true;
    			break;
    		    }
    	    }
    
    	    if (!isOld){
    		    List<String> L = new ArrayList();
    	    	L.add(s);
    		    LL.add(L);
        	}	
        }
    	return LL;
    }
    
    boolean isAligned(String s1, String s2){
    	if (s1.length() != s2.length()) return false;
    
    	int dis = -1;
    	for (int i = 0; i < s1.length(); i++){
        	char c1 = s1.charAt(i), c2 = s2.charAt(i);
        	if (dis == -1) dis = (c2 + 26 - c1) % 26;
        	else{
    	         if ( (c2+ 26 - c1) % 26 != dis) return false;
        	}
    	}
    	return true;
    }

  • 0

    This is O(n^2) worst case, right? When all strings belong to different groups. And yet it is still efficient?


Log in to reply
 

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