leetcode 242,leetcode438,leetcode49

素颜马尾好姑娘i 2023-06-16 07:57 149阅读 0赞

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = “anagram”, t = “nagaram”  
输出: true  
示例 2:

输入: s = “rat”, t = “car”  
输出: false  
说明:  
你可以假设字符串只包含小写字母。

进阶:  
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路：桶排序

public boolean isAnagram(String s, String t) {
        
            
            //数组来隐射
            int[] nums = new int[27];
            
            for(char c:s.toCharArray())
            {
        
                nums[c-'a']++;
            }
            
            for(char n:t.toCharArray())
            {
        
                nums[n-'a']--;
            }
            
            for(int i:nums)
            {
        
                if(i!=0)
                    return false;
            }
            return true;
        }

**leetcode 438找到字符串中所有字母异位词**

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。  
不考虑答案输出的顺序。  
示例 1:

输入:  
s: “cbaebabacd” p: “abc”

输出:  
\[0, 6\]

解释:  
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。  
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。  
示例 2:

输入:  
s: “abab” p: “ab”

输出:  
\[0, 1, 2\]

解释:  
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。  
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。  
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。

思路： 滑动窗口问题，用两个数组来判断做桶，然后开始滑动，如果满足条件就加入l，否则移动l++指针，同时去除桶中l的影响。

class Solution \{  
public List findAnagrams(String s, String p) \{  
List list = new ArrayList<>();  
char\[\] pchar = p.toCharArray();  
int\[\] snums = new int\[26\];  
int\[\] pnums = new int\[26\];

//子表
        for(char c:pchar){
            pnums[c-'a']++;
        }
    
        int l = 0,r = 0;
        while(r<s.length()){
    
            snums[s.charAt(r)-'a']++;
            r++;
    
    
            while(isSubSet(snums,pnums)){
                // l++;
                if(r-l == p.length())
                    list.add(l);
                snums[s.charAt(l)-'a']--;
                l++;
            }
        }
        return list;
    }
    
    public boolean isSubSet(int[] snums,int[] pnums){
    
        for(int i = 0;i<pnums.length;i++){
    
            if(pnums[i]!=0 && pnums[i]>snums[i])
            {
                return false;
            }
        }
        return true;
    }

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: \[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”\],  
输出:  
\[  
\[“ate”,“eat”,“tea”\],  
\[“nat”,“tan”\],  
\[“bat”\]  
\]  
说明：

所有输入均为小写字母。  
不考虑答案输出的顺序。  
在真实的面试中遇到过这道题？

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            List<List<String>> res = new ArrayList<>();
            if (strs == null || strs.length == 0)
                return res;
                int m = 0;
            Map<String,Integer> map = new HashMap<>();
            for (int i = 0;i < strs.length;i++) {
        
                char[] c1 = strs[i].toCharArray();
               Arrays.sort(c1);
                String s1 = new String(c1);
                if (!map.containsKey(s1)) {
        
                    map.put(s1,m++);
                }
            }
            for (int i = 0;i < m;i++) {
        
                res.add(new ArrayList<String>());
            }
    
            for (int i = 0;i < strs.length;i++) {
        
               char[] c1 = strs[i].toCharArray();
               Arrays.sort(c1);
                String s1 = new String(c1);
                int index = map.get(s1);
              
                res.get(index).add(new String(strs[i]));
                
    
            }
            return res;
        }
    }