Posted Updated LeetCode / Easy / 复习2 minutes read (About 299 words)

290. Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

先将s分割成数组。
如果words的长度和pattern的长度不同则返回false。
用长度为26的数组储存pattern的字符。
同时遍历words和pattern，将pattern的字符换算成数字作为index，将words[i]填入数组。
如果数组中已经有word存在，则检查新的word和数组内的word是否相等。
如果不相等，则返回false。

最后遍历数组，比对各个字符中对应的word是否相等，如果有相等的，则返回false。由于数组长度固定，因此这个操作的时间复杂度是O(1)。

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
class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        String[] alphabet = new String[26];
        
        if(words.length != pattern.length()){
            return false;
        }
        
        for(int i = 0; i < pattern.length(); i++){
            
            if( alphabet[pattern.charAt(i) - 'a'] != null){
                if(!alphabet[pattern.charAt(i) - 'a'].equals(words[i])){
                    return false;
                }
            }
            else{
                alphabet[pattern.charAt(i) - 'a']  = words[i];
            }
        }
        
        for(int i = 0; i < alphabet.length; i++){
            for(int j = i+1; j < alphabet.length; j++){
                if(alphabet[i] == null || alphabet[j] == null){
                    continue;
                }
                if(alphabet[i].equals(alphabet[j])){
                    return false;
                }
            }
        }
        
        return true;
    }
}
Posted Updated LeetCode / Easya minute read (About 137 words)

119. Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

根据杨辉三角形的规则递归。
每次递归行数-1。
根据上一行的返回值，生成新行的列表，然后返回。
如果生成行数为0则返回{1}。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> getRow(int rowIndex) {
        if(rowIndex == 0){
            List<Integer> ret = new ArrayList();
            ret.add(1);
            return ret;
        }
        
        List<Integer> arr = getRow(rowIndex - 1);
        List<Integer> ret = new ArrayList();
        
        for(int i = 0; i < arr.size()+1; i++){
            if(i == 0 || i == arr.size()){
                ret.add(1);
            }
            else{
                ret.add(arr.get(i) + arr.get(i-1));
            }
        }
        return ret;
    }
}
Follow

Recents

Archives

Links

×