Simple O(N^2) solution


  • 0
    I
    public class Solution {
        public List<List<String>> groupStrings(String[] strings) {
            List<List<String>> res = new ArrayList<List<String>>();
            if(strings.length == 0) {
                return res;
            }
            
            boolean[] taken = new boolean[strings.length];
            
            for(int i = 0; i < strings.length; i++) {
                if(taken[i]) {
                    continue;
                }
                
                List<String> data = new ArrayList<String>();
                data.add(strings[i]);
                taken[i] = true;
                for(int j = i + 1; j < strings.length; j++) {
                    if(!taken[j] && match(strings[i], strings[j])) {
                        taken[j] = true;
                        data.add(strings[j]);
                    }
                }
                
                res.add(data);
            }
            
            return res;
        }
        
        boolean match(String s1, String s2) {
            if(s1.length() != s2.length()) {
                return false;
            }
            
            if(s1.isEmpty()) {
                return true;
            }
            
            int dist = s2.charAt(0) - s1.charAt(0);
            for(int i = 0; i < s1.length(); i++) {
                int ax = 'a' + ((s1.charAt(i) - 'a') + dist + 26) % 26;
                if(s2.charAt(i) != (char)ax) {
                    return false;
                }
            }
            
            return true;
        }
    }
    

Log in to reply
 

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