1. Valid Letter Words

Given two strings s and t, write a function to determine whether t is an alphabetic ectopic word of s.

Note: if each character in S and t occurs the same number of times, s and T are called alphabetic words.

Valid Letter ectopic words

Idea:
1. Create an array with a size of 26 to record the number of occurrences of each lowercase letter
2. Collect the letters in the two strings respectively
3. Check whether the array is 0

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];

        //Collect the number and type of each letter in s and put it in the array
        for(char ch:s.toCharArray()){
            record[ch-'a']+=1;
        }

        //Compare with the number and type of each letter in t
        for(char ch:t.toCharArray()){
            record[ch-'a']-=1;
        }

        //See whether the current array element is 0
        for(int i : record){
            if(i!=0)  return false;
        }

        return true;
    }
}

2. Ransom letter

Give you two strings: ransomNote and magazine. Judge whether ransomNote can be composed of characters in magazine. If yes, return true; Otherwise, false is returned. Each character in magazine can only be used once in ransomNote.

Ransom letter

Idea: ibid

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] record =new int[26];

        //Collect the number and type of characters in ransomNote
        for(char ch:ransomNote.toCharArray()){
            record[ch-'a']+=1;
        }

        //Release the characters and quantity of the magazine
        for(char ch:magazine.toCharArray()){
            record[ch-'a']-=1;
        }

        //Traverse the number of letters in the record
        for(int i :record){
            if(i>0)  return false;  
        }
        return true;
    }
}

3. Grouping of letter words

I'll give you an array of strings. Please combine letters and words together. You can return a list of results in any order.

An alphabetic ectopic word is a new word obtained by rearranging the letters of the source word. The letters in all the source words are usually used just once.

Alphabetic word grouping

1. Create a hash table
2. Convert strings into character arrays and sort them alphabetically.
3. Convert the sorted character array into a string and use it as the key value of the hash table
4. Compare whether the hash table has a key value. If not, put the key value into the table
5. Put the value value corresponding to the key into the table

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs==null||strs.length==0){
            return new ArrayList();
        }

        Map<String, List> map = new HashMap<String ,List>();
        for(String s : strs){
            //Convert string to character array
            char[] chs = s.toCharArray();
            //Sort character arrays alphabetically
            Arrays.sort(chs);
            //The sorted string is used as the key value in the hash table
            String key = String.valueOf(chs);
            //Determine whether there is a key value in the hash table
            if(!map.containsKey(key)){
                map.put(key,new ArrayList());
            }
            //Put the string in the list of the corresponding key
            map.get(key).add(s);//Get the corresponding val according to the key and put it in the list
        }
        return new ArrayList(map.values());
    }
}

4. Find all letter ectopic words in the string

Given two strings S and p, find the substrings of all ectopic words of p in s, and return the starting indexes of these substrings. The order in which answers are output is not considered.

Ectopic words refer to strings formed by rearrangement of the same letters (including the same string).

Find all alphabetic words in the string

Idea:
1. Create two arrays of size 26 to record the number of letters
2. Count the number of letters within the length range based on the length of p
3. If two arrays equal, add 0 to the list
4. Record the remaining length array in s, and delete the old letters while recording the number of new letters.
5. If the two arrays are equal, put the current subscript into the list.

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList();//Used to store answers
        int[] sRecord = new int[26];
        int[] pRecord = new int[26];
        int sLen = s.length();
        int pLen = p.length();
        if(sLen<pLen){
            return ans;
        }

        //Count the number of letters in the string and put them in two arrays respectively. First, take the shorter one as the benchmark
        for(int i =0;i<pLen;i++){
            sRecord[s.charAt(i)-'a']++;
            pRecord[p.charAt(i)-'a']++;
        }
        //If the two arrays are identical, the 0 position is output
        if(Arrays.equals(sRecord,pRecord)){
            ans.add(0);
        }
        //Count the number of characters left in s
        for(int i =pLen;i<sLen;i++){
            sRecord[s.charAt(i-pLen)-'a']--;//Empty s array
            sRecord[s.charAt(i)-'a']++;
            //If the two arrays are exactly equal at this time
            if(Arrays.equals(sRecord,pRecord)){
               ans.add(i-pLen+1);
            }
        }
        return ans;
    }
}