[leetcode] day96 - the first unique character & ransom letter & letter ectopic word

1. The first unique character in the string

387. The first unique character in the string 【 Simple 】

Answer key

Storage frequency using hash table , Here the hash table is used HashMap

class Solution {
    
    public int firstUniqChar(String s) {
    
        Map<Character,Integer>hashMap=new HashMap<>();
        for(int i=0;i<s.length();i++){
    
            char c=s.charAt(i);
            if(hashMap.containsKey(c)){
    
                int count=hashMap.get(c);
                hashMap.put(c,count+1);
            }
            else
                hashMap.put(c,1);
        }
        for(int i=0;i<s.length();i++){
    
            if(hashMap.get(s.charAt(i))==1)
                return i;
        }
        return -1;
    }
}

Time complexity ：$O(n)$

Spatial complexity ：$O(\mid \Sigma \mid )$, among $\Sigma$ It's a character set.

2. Ransom letter

383. Ransom letter 【 Simple 】

Answer key

Storage frequency using hash table , Here the hash table is used Array , Less time to run

class Solution {
    
    public boolean canConstruct(String ransomNote, String magazine) {
    
        int[] cnt=new int[26];
        for(int i=0;i<magazine.length();i++){
    
            cnt[magazine.charAt(i)-'a']++;
        }
            
        for(int i=0;i<ransomNote.length();i++){
    
            char c=ransomNote.charAt(i);
            if(cnt[c-'a']<=0)
                return false;
            cnt[c-'a']--;
        }
        return true;
    }
}

Time complexity ：$O(m+n)$

Spatial complexity ：$O(\mid \Sigma \mid )$, among $\Sigma$ It's a character set.

3. Effective alphabetic words

242. Effective alphabetic words 【 Simple 】

Answer key

Hashtable

class Solution {
    
    public boolean isAnagram(String s, String t) {
    
        int m=s.length(),n=t.length();
        if(m!=n)
            return false;
        int[] snt=new int[26];
        for(int i=0;i<m;i++)
            snt[s.charAt(i)-'a']++;
        for(int i=0;i<n;i++){
    
            snt[t.charAt(i)-'a']--;
            if(snt[t.charAt(i)-'a']<0)
                return false;   
        }
        return true;
    }
}

Be careful ： Mentioned in the advanced “ If the input string contains unicode character What do I do ”？
In this case, the hash table cannot be represented by an array , and Only use HashMap！

Time complexity ：$O(n)$

Spatial complexity ：$O(\mid \Sigma \mid )$, among $\Sigma$ It's a character set.

Sort

t yes s The heterotopic words of are equivalent to 「 Two strings are sorted equal 」. So we can do string s and t Sort them separately , You can judge whether the sorted strings are equal .

Just remember String to array 、 Sort 、 Sentence etc. The operation of API

class Solution {
    
    public boolean isAnagram(String s, String t) {
    
        int m=s.length(),n=t.length();
        if(m!=n)
            return false;
        char[] str1=s.toCharArray();
        char[] str2=t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1,str2);
    }
}

Time complexity ：$O(nlogn)$, Sort required

Spatial complexity ：$O(logn)$, Sort required