Leetcode Review(5)

Posted on | In |

Leetcode 438 Find All Anagrams in a String

There are several substring questions in leetcode.

And fortunately we can use a template to solve them.

Description:

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Methods:

I need to use Chinese to make me understand my thinking. LOL

还是用中文吧。

滑动窗口可以解决很多子字符串的问题

使用两个指针left&right，来作为窗口的边界。count作为t和窗口中字符串的差异的个数。

用hash table来判断anagram的问题，也是一种非常好的方式。

如果hash[i]中的数字大于0，则说明在t里面有相应的char，差异减小，window增大。

如果差异减到0，则把左边界加入。

然后再移动左边界「如果hash（left）里的数》=0，则说明left的char是有效的，是出现在t中的，这个时候移动了左边界，则要对左边界进行补偿，所以count要增加」

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int ls = s.length();
        int lp = p.length();
        List<Integer> list = new ArrayList<>();
        if(ls==0 || lp==0) return list;
        
        int[] hash = new int[26];
        char[] array = p.toCharArray();
        for(char c:array)
            hash[c-'a']++;
        
        int count=lp, start=0, end=0;
        
        while(end<ls){
            if(hash[s.charAt(end)-'a']>0)
                count--;
            hash[s.charAt(end)-'a']--;
            end++;
            
            if(count==0)
                list.add(start);
            
            if(end-start==lp){
                if(hash[s.charAt(start)-'a']>=0)
                    count++;
                hash[s.charAt(start)-'a']++;
                start++;
            }          
        }
        return list;       
    }
}

Leetcode 76 Minimum Window Substring

Description:

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Methods:

这题就可以用上述的template。虽然是hard，但是我居然自己写出来了哈哈哈。

这个是上述问题的变种。

右边界的方法是不变的，问题是左边界。

左边界要移动有两种可能性：

  1. 当count==0，即差异为0的时候，说明t在window里都找到了。这时候我们需要确定左边有没有冗余的东西可以删除。
  2. 当count==0，我们更新完最小字串的信息之后，需要滑动窗口。同样的，如果曾经出现在窗口里的字符被移动出去，我们需要对count++补偿。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public String minWindow(String s, String t) {
        int lt = t.length();
        int ls = s.length();
        int minL=Integer.MAX_VALUE;
        String min="";
        int[] hash = new int[256];
        char[] array = t.toCharArray();
        for(char c: array)
            hash[c]++;
            
        int count=lt,left=0,right=0;
        while(right<ls){
            if(hash[s.charAt(right)]>0)
                count--;
            hash[s.charAt(right)]--;
            right++;
            
            if(count==0){
                while(hash[s.charAt(left)]<0){
                    hash[s.charAt(left)]++;
                    left++;
                }
                
                
                if(minL>right-left){
                    minL=right-left;
                    min=s.substring(left,right);
                }
                if(hash[s.charAt(left)]>=0)
                    count++;
                hash[s.charAt(left)]++;
                left++;
            }            
            }
        return min;
        
    }
}

Leetcode 200 Number of Islands

Description:

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Methods:

Use dfs.

Everytime we encounter an ‘1’, we try to turn the island around this ‘1’ into 0, so we won’t count repeatedly.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length;
        if(m==0) return 0;
        int n = grid[0].length;
        int count=0;
        
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    dfs(grid,i,j,m,n);
                    count++;
                    
                }
            }
        }
        return count;
    }
    
    public void dfs(char[][] grid,int i, int j, int m, int n){
        if(i<0 || i>=m || j<0 || j>=n || grid[i][j]!='1')
            return;
        grid[i][j]='0';
        dfs(grid,i+1,j,m,n);
        dfs(grid,i-1,j,m,n);
        dfs(grid,i,j+1,m,n);
        dfs(grid,i,j-1,m,n);
    }   
}