Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<String, Character> str2ch = new HashMap<>();
        Map<Character, String> ch2str = new HashMap<>();
        int n = str.length();
        int i = 0;
        for (char ch : pattern.toCharArray()) {
            if (i >= n) return false;
            int j = i;
            while (j < n && str.charAt(j) != ' ') j++;
            String tmp = str.substring(i, j);
            if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) return false;
            if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) return false;
            str2ch.put(tmp, ch);
            ch2str.put(ch, tmp);
            i = j + 1;
        }
        return i >= n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, int> p2i;
        unordered_map<string, int> w2i;
        istringstream in(str);
        int i = 0, n = pattern.size();
        for (string word; in >> word; ++i) {
            if (i == n || p2i[pattern[i]] != w2i[word])
                return false;
            p2i[pattern[i]] = w2i[word] = i + 1;
        }
        return i == n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        word2ch = dict()
        ch2word = dict()
        words = s.split()
        if len(pattern) != len(words): return False
        for ch, word in zip(pattern, words):
            if (word in word2ch and word2ch[word] != ch) or (ch in ch2word and ch2word[ch] != word):
                return False
            word2ch[word] = ch
            ch2word[ch] = word
        return True

Posted on Edited on In 
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
class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
        List<Integer> ans = new ArrayList<>();
        backtrack(S, 0, 0,  0, ans);
        return ans;
    }

    private boolean backtrack(String S, int index, int sum, int prev, List<Integer> ans) {
        if (index == S.length())
            return ans.size() >= 3;
        long currLong = 0;
        for (int i = index; i < S.length(); i++) {
            if (i > index && S.charAt(index) == '0') break;
            currLong = currLong * 10 + S.charAt(i) - '0';
            if (currLong > Integer.MAX_VALUE) break;
            int curr = (int) currLong;
            if (ans.size() >= 2) {
                if (curr < sum) continue;
                if (curr > sum) break;
            }
            ans.add(curr);
            if (backtrack(S, i + 1, prev + curr, curr, ans))
                return true;
            ans.remove(ans.size() - 1);
        }
        return false;
    }
}
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:
    vector<int> splitIntoFibonacci(string S) {
        vector<int> ans;
        const int len = S.size();
        function<bool(int, int, int)> backtrack = [&](int index, int sum, int prev) {
            if (index == len) {
                return ans.size() >= 3;
            }
            long long curr = 0;
            for (int i = index; i < len; ++i) {
                if (i > index && S[index] == '0') break;
                curr = curr * 10 + S[i] - '0';
                if (curr > INT_MAX) break;
                if (ans.size() >= 2) {
                    if (curr < sum) continue;
                    if (curr > sum) break;
                }
                ans.push_back(curr);
                if (backtrack(i + 1, prev + curr, curr))
                    return true;
                ans.pop_back();
            }
            return false;
        };
        backtrack(0, 0, 0);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def splitIntoFibonacci(self, S: str) -> List[int]:
        ans = list()
        def backtrack(index: int):
            if index == len(S):
                return len(ans) >= 3
            curr = 0
            for i in range(index, len(S)):
                if i > index and S[index] == "0": break
                curr = curr * 10 + ord(S[i]) - ord("0")
                if curr > 2**31 - 1: break
                if len(ans) >= 2:
                    if curr < ans[-2] + ans[-1]: continue
                    if curr > ans[-2] + ans[-1]: break
                ans.append(curr)
                if backtrack(i + 1):
                    return True
                ans.pop()
            return False

        backtrack(0)
        return ans
0%