发表于 | 分类于

Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.

Example 1:

1
2
Input: 12
Output: 21

Example 2:

1
2
Input: 21
Output: -1

解法1：

用next permutation的算法来解，先把n转换成一个数字的数组，然后接下的算法就是一致的了。
要注意的是算出来的答案可能会overflow,所以要判断一下是否overflow。
C++

1

Java

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Solution {
    public int nextGreaterElement(int n) {
        int len = (int)Math.log10(n) + 1;
        int[] digits = new int[len];
        int i = len - 1;
        while (n > 0) {
            digits[i--] = n % 10;
            n /= 10;
        }
        // Use the next permutation algorithm
        int pivot = -1;
        for (i = len - 2; i >= 0; i--) {
            if (digits[i] < digits[i + 1]) {
                pivot = i;
                break;
            }
        }
        if (pivot == -1) {
            return -1;
        }
        for (i = len - 1; i > pivot; i--) {
            if (digits[i] > digits[pivot]) {
                int temp = digits[i];
                digits[i] = digits[pivot];
                digits[pivot] = temp;
                break;
            }
        }
        int j;
        for (i = pivot + 1, j = len - 1; i < j; i++,j--) {
            int temp = digits[i];
            digits[i] = digits[j];
            digits[j] = temp;
        }
        // combine
        int res = 0;
        for (i = 0; i < len; i++) {
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && res % 10 > Integer.MAX_VALUE % 10)) {
                return -1;
            }
            res = res * 10 + digits[i];
        }
        return res;
    }
}

发表于 | 分类于

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.

Machine 1 (sender) has the function:

1
2
3
4
string encode(vector<string> strs) {
 // ... your code
 return encoded_string;
}

Machine 2 (receiver) has the function:

1
2
3
4
vector<string> decode(string s) {
 //... your code
 return strs;
}

So Machine 1 does:

1
string encoded_string = encode(strs);

and Machine 2 does:

1
vector<string> strs2 = decode(encoded_string);

strs2 in Machine 2 should be the same as strs in Machine 1.

Implement the encode and decode methods.

Note:

The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.

解法1：

把每一个string里的字符转换成ascii码，用一个＃分隔。同时每一个字符串间用，分隔。
要注意的是，在decode的时候可能会出现,,的情况，所以要用string.split(pattern, -1)来保留所有的empty string

C++

1

Java

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
40
41
42
43
44
45
46
public class Codec {
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
       StringBuilder builder = new StringBuilder();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            for (char c : chars) {
                builder.append("" + Integer.toString((int)c));
                builder.append("#");
            }
            builder.append(",");
            // if (!str.length() == 0) {
            //     builder.append("#");
            // }
        }
        return builder.toString();
    }
    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.isEmpty()) {
            return res;
        }
        String[] components = s.substring(0, s.length() - 1).split(",",-1);    // Remove the "," at the end of the string
        for (String element : components) {
            StringBuilder builder = new StringBuilder();
            String[] codes = element.split("#");
            for (String code : codes) {
                if (!code.isEmpty()) {
                    builder.append((char)Integer.parseInt(code));
                }
            }
            res.add(builder.length() == 0 ? "" : builder.toString());
        }
        return res;        
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

解法2：

把一个string转化为size/stringcontent的形式。

lang: java
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
public class Codec {
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str.length()).append("/").append(str);
        }
        return sb.toString();
    }
    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> res = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int pos = s.indexOf('/', i);
            int len = Integer.parseInt(s.substring(i, pos));
            res.add(s.substring(pos + 1, pos + 1 + len));
            i = pos + 1 + len;
        }
        return res;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));

发表于 | 分类于

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

“3+2*2” = 7
“ 3/2 “ = 1
“ 3+5 / 2 “ = 5

Note: Do not use the eval built-in library function.

解法1：

用一个stack来存储中间结果。遇上×，／的时候计算之前的操作，遇上＋／－的时候只有在之前的操作为同一优先级的时候才计算。
写的比较繁琐，不如leetcode上的答案好。答案里不需要有stack, 用一个preVal来记录上一个计算的结果，只有当当前操作为加或者减的时候才需要把上一次更新的结果并入最终的结果。
C++

1

Java

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class Solution {
    public int calculate(String s) {
        Stack<Integer> operands = new Stack<Integer>();
        Stack<String> operators = new Stack<String>();
        int i = 0;
        while (i < s.length()) {
            if (s.charAt(i) == ' ') {
                i++;
                continue;
            } else if (s.charAt(i) == '+' || s.charAt(i) == '-'){
                if (!operators.empty()) {
                    int right = operands.pop();
                    int left = operands.pop();
                    String last = operators.pop();
                    if (last.equals("+")) {
                        operands.push(left + right);
                    } else if (last.equals("-")) {
                        operands.push(left - right);
                    } else if (last.equals("*")) {
                        operands.push(left * right);
                    } else {
                        operands.push(left / right);
                    }
                }
                operators.push(s.substring(i, i + 1));
                i++;
            } else if (s.charAt(i) == '*' || s.charAt(i) == '/') {
                if (!operators.empty()) {
                    String last = operators.peek();
                    if (last.equals("*")) {
                        operators.pop();
                        int right = operands.pop();
                        int left = operands.pop();
                        operands.push(left * right);
                    } else if (last.equals("/")) {
                        operators.pop();
                        int right = operands.pop();
                        int left = operands.pop();
                        operands.push(left / right);
                    }
                }
                operators.push(s.substring(i, i + 1));
                i++;
            } else {
                int j = i + 1;
                while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                    j++;
                }
                int element = Integer.parseInt(s.substring(i, j));
                // check if there is valid * or / operators
                if (!operators.empty()) {
                    if (operators.peek().equals("*")) {
                        operators.pop();
                        int left = operands.pop();
                        operands.push(left * element);
                    } else if (operators.peek().equals("/")) {
                        operators.pop();
                        int left = operands.pop();
                        operands.push(left / element);
                    } else {
                        operands.push(element);
                    }
                } else {
                    operands.push(element);                
                }
                i = j;
            }
        }
        // empty operators until it is empty
        while (!operators.empty()) {
            String operator = operators.pop();
            int right = operands.pop();
            int left = operands.pop();
            if (operator.equals("*")) {
                operands.push(left * right);
            } else if (operator.equals("/")) {
                operands.push(left / right);
            } else if (operator.equals("+")) {
                operands.push(left + right);
            } else {
                operands.push(left - right);
            }
        }
        return operands.pop();
    }
}

###解法２：　###
答案来自与leetcode
Java

lang: java
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
public int calculate(String s) {
    if (s == null) return 0;
    s = s.trim().replaceAll(" +", "");
    int length = s.length();
    int res = 0;
    long preVal = 0; // initial preVal is 0
    char sign = '+'; // initial sign is +
    int i = 0;
    while (i < length) {
        long curVal = 0;
        while (i < length && (int)s.charAt(i) <= 57 && (int)s.charAt(i) >= 48) { // int
            curVal = curVal*10 + (s.charAt(i) - '0');
            i++;
        }
        if (sign == '+') {
            res += preVal;  // update res
            preVal = curVal;
        } else if (sign == '-') {
            res += preVal;  // update res
            preVal = -curVal;
        } else if (sign == '*') {
            preVal = preVal * curVal; // not update res, combine preVal & curVal and keep loop
        } else if (sign == '/') {
            preVal = preVal / curVal; // not update res, combine preVal & curVal and keep loop
        }
        if (i < length) { // getting new sign
            sign = s.charAt(i);
            i++;
        }
    }
    res += preVal;
    return res;
}

发表于 | 分类于

Given two strings S and T, determine if they are both one edit distance apart.

解法1：

这题一开始如果用dp做的话需要O(MN)的复杂度，TLE了。那么一定有更简便的方法。
这里呢用到了edit distance的性质。对于edit distance为１的两个string,只可能存在下面三种情况。
长度相等 => 有且仅有一个字符不一样
长度不相等，　那么如果删掉左面string的一个字符或者是右面的一个字符。
最后还要比较一下两者的长度是否只差１。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        for (int i = 0; i < Math.min(m, n); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (m == n) {
                    return s.substring(i+1).equals(t.substring(i+1));
                } else if (m > n) {
                    return s.substring(i+1).equals(t.substring(i));
                } else {
                    return s.substring(i).equals(t.substring(i+1));
                }
            }
        }
        return Math.abs(m - n) == 1;
    }
}

发表于 | 分类于

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:
Input: [1000,100,10,2]
Output: “1000/(100/10/2)”
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in “1000/((100/10)/2)” are redundant,
since they don’t influence the operation priority. So you should return “1000/(100/10/2)”.

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2
Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

解法1：O(N^3)

这题的数学解法比较无聊，也不觉得对锻炼思路有帮助。倒是这个divide & conquer的解法很清楚明白。题目一拿到比较懵，如果细细思考可以想到。要得到最大值，需要dividend最大,divisor最小。那么就可以不停的尝试分割的位置，然后维护每一个子段的最大最小值以及产生最大最小值分割的括号摆放字符串。这里就需要用一个辅助class。
同时为了减少time complexity, 用一个二维数组做memorization来记录每一个子串的中间结果。

C++

1

Java

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
40
41
public class Solution {
    class T {
        float max_val, min_val;
        String min_str, max_str;
    }
    public String optimalDivision(int[] nums) {
        T[][] memo = new T[nums.length][nums.length];
        T t = optimal(nums, 0, nums.length - 1, "", memo);
        return t.max_str;
    }
    public T optimal(int[] nums, int start, int end, String res, T[][] memo) {
        if (memo[start][end] != null)
            return memo[start][end];
        T t = new T();
        if (start == end) {
            t.max_val = nums[start];
            t.min_val = nums[start];
            t.min_str = "" + nums[start];
            t.max_str = "" + nums[start];
            memo[start][end] = t;
            return t;
        }
        t.min_val = Float.MAX_VALUE;
        t.max_val = Float.MIN_VALUE;
        t.min_str = t.max_str = "";
        for (int i = start; i < end; i++) {
            T left = optimal(nums, start, i, "", memo);
            T right = optimal(nums, i + 1, end, "", memo);
            if (t.min_val > left.min_val / right.max_val) {
                t.min_val = left.min_val / right.max_val;
                t.min_str = left.min_str + "/" + (i + 1 != end ? "(" : "") + right.max_str + (i + 1 != end ? ")" : "");
            }
            if (t.max_val < left.max_val / right.min_val) {
                t.max_val = left.max_val / right.min_val;
                t.max_str = left.max_str + "/" + (i + 1 != end ? "(" : "") + right.min_str + (i + 1 != end ? ")" : "");
            }
        }
        memo[start][end] = t;
        return t;
    }
}

发表于 | 分类于

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

1
0.1 < 1.1 < 1.2 < 13.37

解法1：

应该算简单题。要注意的一点是java里string.split(regex), 如果是特殊字符比如”.”的时候，要注意escape。然后每一位比较，如果有一个字符串比较短，就把他对应的位看成是0。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        for (int i =  0; i < Math.max(v1.length, v2.length); i++) {
             int v1number = i < v1.length ? Integer.parseInt(v1[i]) : 0;
            int v2number = i < v2.length ? Integer.parseInt(v2[i]) : 0;
            if (v1number > v2number) {
                return 1;
            } else if (v1number < v2number) {
                return -1;
            }
        }
        return 0;
    }
}

发表于 | 分类于

During the NBA playoffs, we always arrange the rather strong team to play with the rather weak team, like make the rank 1 team play with the rank nth team, which is a good strategy to make the contest more interesting. Now, you’re given n teams, you need to output their final contest matches in the form of a string.

The n teams are given in the form of positive integers from 1 to n, which represents their initial rank. (Rank 1 is the strongest team and Rank n is the weakest team.) We’ll use parentheses(‘(‘, ‘)’) and commas(‘,’) to represent the contest team pairing - parentheses(‘(‘ , ‘)’) for pairing and commas(‘,’) for partition. During the pairing process in each round, you always need to follow the strategy of making the rather strong one pair with the rather weak one.

Example 1:

1
2
3
4
5
Input: 2
Output: (1,2)
Explanation:
Initially, we have the team 1 and the team 2, placed like: 1,2.
Then we pair the team (1,2) together with '(', ')' and ',', which is the final answer.

Example 2:

1
2
3
4
5
6
7
Input: 4
Output: ((1,4),(2,3))
Explanation:
In the first round, we pair the team 1 and 4, the team 2 and 3 together, as we need to make the strong team and weak team together.
And we got (1,4),(2,3).
In the second round, the winners of (1,4) and (2,3) need to play again to generate the final winner, so you need to add the paratheses outside them.
And we got the final answer ((1,4),(2,3)).

Example 3:

1
2
3
4
5
6
7
Input: 8
Output: (((1,8),(4,5)),((2,7),(3,6)))
Explanation:
First round: (1,8),(2,7),(3,6),(4,5)
Second round: ((1,8),(4,5)),((2,7),(3,6))
Third round: (((1,8),(4,5)),((2,7),(3,6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).

Note:
The n is in range [2, 212].
We ensure that the input n can be converted into the form 2k, where k is a positive integer.

解法1：

题目一开始没理解。主要的思路就是每次缩短1/2，把排名第一的组合和排名最后的组合放在一起。
用递归或者是iteration都可以做。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public String findContestMatch(int n) {
        List<String> matches = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            matches.add("" + i);
        }
        while (matches.size() != 1) {
            List<String> round = new ArrayList<>();
            for (int i = 0; i < matches.size() / 2; i++) {
                round.add("(" + matches.get(i) + "," + matches.get(matches.size() - 1 -i) + ")");
            }
            matches = round;
        }
        return matches.get(0);
    }
}

发表于 | 分类于

You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Design a log storage system to implement the following functions:

void Put(int id, string timestamp): Given a log’s unique id and timestamp, store the log in your storage system.

int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = “2017:01:01:23:59:59”, end = “2017:01:02:23:59:59”, granularity = “Day”, it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.

Example 1:

1
2
3
4
5
put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:
There will be at most 300 operations of Put or Retrieve.
Year ranges from [2000,2017]. Hour ranges from [00,23].
Output for Retrieve has no order required.

解法1：

用一个hashmap来存储log,这题的考点主要在retrieve上。retrieve的时候可以按照gra来截取相关的子串，然后和start, end直接比较大小就可以。
C++

1

Java

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class LogSystem {
    HashMap<Integer, String> map;
    public LogSystem() {
        map = new HashMap<Integer, String>();
    }
    public void put(int id, String timestamp) {
        map.put(id, timestamp);
    }
    public List<Integer> retrieve(String s, String e, String gra) {
        List<Integer> res = new ArrayList<Integer>();
        int x = 0;
        switch (gra) {
            case "Year":
                x = 4;
                break;
            case "Month":
                x = 7;
                break;
            case "Day":
                x = 10;
                break;
            case "Hour":
                x = 13;
                break;
            case "Minute":
                x = 16;
                break;
            case "Second":
                x = 19;
                break;
        }
        String start = s.substring(0, x);
        String end = e.substring(0, x);
        for (int id : map.keySet()) {
            String record = map.get(id).substring(0,x);
            if (record.compareTo(start) >= 0 && record.compareTo(end) <= 0) {
                res.add(id);
            }
        }
        return res;
    }
}
/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * List<Integer> param_2 = obj.retrieve(s,e,gra);
 */

发表于 | 分类于

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

Example 1:

1
2
3
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Note:
The length of given words won’t exceed 500.
Characters in given words can only be lower-case letters.

解法1：

这题和edit distance的思路一样。用二维dp即可解决。
C++

1

Java

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
public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        // first row
        for (int i = 0; i <= n; i++) {
            dp[0][i] = i;
        }
        // first col
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1]));
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 2));
                }
            }
        }
        return dp[m][n];
    }
}

发表于 | 分类于

Given a string s and a list of strings dict, you need to add a closed pair of bold tag and to wrap the substrings in s that exist in dict. If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag. Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

Example 1:

1
2
3
4
5
Input:
s = "abcxyz123"
dict = ["abc","123"]
Output:
"<b>abc</b>xyz<b>123</b>"

Example 2:

1
2
3
4
5
Input:
s = "aaabbcc"
dict = ["aaa","aab","bc"]
Output:
"<b>aaabbc</b>c"

Note:
The given dict won’t contain duplicates, and its length won’t exceed 100.
All the strings in input have length in range [1, 1000].

解法1：

这题可以分成两个部分，第一个部分是找出来所有在字典中出现的词。
这一步可以遍历字典，按照每一个词的长度来遍历原字符串来找出出现的位置。可以用一个array来存储每一个词出现的(start, end)。
然后问题就变成，要把这些pair先merge一下，然后头尾加上tag即可。
C++

1

Java

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
public class Solution {
    public String addBoldTag(String s, String[] dict) {
        List<int[]> pairs = new ArrayList<int[]>();
        for (String d : dict) {
            int len = d.length();
            for (int i = 0; i <= s.length() - len; i++) {
                if (d.equals(s.substring(i, i + len))) {
                    pairs.add(new int[] {i,i + len - 1});
                }
            }
        }
        Collections.sort(pairs, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        StringBuilder builder = new StringBuilder();
        int prev = 0;
        for (int i = 0; i < pairs.size(); i++) {
            builder.append(s.substring(prev, pairs.get(i)[0]));
            // Merge intervals
            int start = pairs.get(i)[0];
            int end = pairs.get(i)[1];
            while (i < pairs.size() - 1 && pairs.get(i + 1)[0] <= end + 1) {
                end = Math.max(end, pairs.get(i + 1)[1]);
                i++;
            }
            builder.append("<b>" + s.substring(start, end + 1) + "</b>");
            prev = end + 1;
        }
        builder.append(s.substring(prev, s.length()));
        return builder.toString();        
    }
}