朱继鹏的博客

天道酬勤，全栈不停

0%

algorithm-string

发表于 更新于 分类于
字串算法

简单

罗马数字转整数

题目描述

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
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

 

示例 1:

输入: s = "III"
输出: 3
示例 2:

输入: s = "IV"
输出: 4
示例 3:

输入: s = "IX"
输出: 9
示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
 

提示：

1 <= s.length <= 15
s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。

题目解答

当前字符比下一个小就是减法，否则就是加法

ps：题目规定了不会出现跨位等情况

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
import java.util.HashMap;
import java.util.Map;

public class Solution {
    Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {
        {
            put('I', 1);
            put('V', 5);
            put('X', 10);
            put('L', 50);
            put('C', 100);
            put('D', 500);
            put('M', 1000);
        }
    };

    public int romanToInt(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues.get(s.charAt(i));
            if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        String s = "III";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase2() {
        String s = "IV";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase3() {
        String s = "IX";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase4() {
        String s = "LVIII";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase5() {
        String s = "MCMXCIV";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }
}

其他解法

解法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
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
92
93
public class Solution {
    public int romanToInt(String s) {
        int v = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (c == 'I') {
                v = v + 1;
            } else if (c == 'V' || c == 'X') {
                if (c == 'V') {
                    v = v + 5;
                } else if (c == 'X') {
                    v = v + 10;
                }

                if (i > 0) {
                    if (chars[i - 1] == 'I') {
                        v = v - 2;
                    }
                }
            } else if (c == 'L' || c == 'C') {
                if (c == 'L') {
                    v = v + 50;
                } else if (c == 'C') {
                    v = v + 100;
                }

                if (i > 0) {
                    if (chars[i - 1] == 'X') {
                        v = v - 20;
                    }
                }
            } else if (c == 'D' || c == 'M') {
                if (c == 'D') {
                    v = v + 500;
                } else if (c == 'M') {
                    v = v + 1000;
                }

                if (i > 0) {
                    if (chars[i - 1] == 'C') {
                        v = v - 200;
                    }
                }
            }
        }

        return v;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        String s = "III";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase2() {
        String s = "IV";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase3() {
        String s = "IX";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase4() {
        String s = "LVIII";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }

    public static void testCase5() {
        String s = "MCMXCIV";

        int result = new Solution().romanToInt(s);
        System.out.println(result);
    }
}

整数转罗马数字

题目描述

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
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给你一个整数，将其转为罗马数字。

 

示例 1:

输入: num = 3
输出: "III"
示例 2:

输入: num = 4
输出: "IV"
示例 3:

输入: num = 9
输出: "IX"
示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
 

提示：

1 <= num <= 3999

题目解答

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
public class Solution {
    int[] values = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
    String[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };

    public String intToRoman(int num) {
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        int num = 3;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase2() {
        int num = 4;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase3() {
        int num = 9;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase4() {
        int num = 58;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase5() {
        int num = 1994;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }
}

其他解法

解法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
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
public class Solution {
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();

        while (num > 0) {
            if (num >= 1000) {
                int x = num / 1000;
                appendChar(sb, 'M', x);

                num = num % 1000;
            } else if (num >= 100) {
                if (num >= 900) {
                    appendChar(sb, 'C');
                    appendChar(sb, 'M');
                } else if (num >= 500) {
                    int x = (num - 500) / 100;
                    appendChar(sb, 'D');
                    appendChar(sb, 'C', x);
                } else if (num >= 400) {
                    appendChar(sb, 'C');
                    appendChar(sb, 'D');
                } else {
                    int x = num / 100;
                    appendChar(sb, 'C', x);
                }

                num = num % 100;
            } else if (num >= 10) {
                if (num >= 90) {
                    appendChar(sb, 'X');
                    appendChar(sb, 'C');
                } else if (num >= 50) {
                    int x = (num - 50) / 10;
                    appendChar(sb, 'L');
                    appendChar(sb, 'X', x);
                } else if (num >= 40) {
                    appendChar(sb, 'X');
                    appendChar(sb, 'L');
                } else {
                    int x = num / 10;
                    appendChar(sb, 'X', x);
                }

                num = num % 10;
            } else {
                if (num >= 9) {
                    appendChar(sb, 'I');
                    appendChar(sb, 'X');
                } else if (num >= 5) {
                    int x = (num - 5) / 1;
                    appendChar(sb, 'V');
                    appendChar(sb, 'I', x);
                } else if (num >= 4) {
                    appendChar(sb, 'I');
                    appendChar(sb, 'V');
                } else {
                    int x = num / 1;
                    appendChar(sb, 'I', x);
                }

                num = 0;
            }
        }

        return sb.toString();
    }

    public void appendChar(StringBuilder sb, char ch) {
        sb.append(ch);
    }

    public void appendChar(StringBuilder sb, char ch, int cnt) {
        for (int i = 0; i < cnt; i++) {
            sb.append(ch);
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        int num = 3;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase2() {
        int num = 4;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase3() {
        int num = 9;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase4() {
        int num = 58;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase5() {
        int num = 1994;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }
}

解法2

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    Map<Integer, Character> symbolValues = new HashMap<Integer, Character>() {
        {
            put(1, 'I');
            put(5, 'V');
            put(10, 'X');
            put(50, 'L');
            put(100, 'C');
            put(500, 'D');
            put(1000, 'M');
        }
    };

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();

        List<Integer> keyList = new ArrayList<>(symbolValues.keySet());
        keyList.sort(null);

        int i = keyList.size() - 1;
        while (i >= 0 && num <= keyList.get(i)) {
            i = i - 2;
        }
        if (i != keyList.size() - 1) {
            i = i + 2;
        }

        while (i - 2 >= 0) {
            int q = keyList.get(i - 2);

            for (int j = i; j >= i - 1; j--) {
                int p = keyList.get(j);

                int x = num / p;
                int y = num % p;

                appendChar(sb, symbolValues.get(p), x);

                if (y + q >= p) {
                    y = y + q - p;

                    appendChar(sb, symbolValues.get(q));
                    appendChar(sb, symbolValues.get(p));
                }

                num = y;
            }

            i = i - 2;
        }

        appendChar(sb, symbolValues.get(1), num);

        return sb.toString();
    }

    public void appendChar(StringBuilder sb, char ch) {
        sb.append(ch);
    }

    public void appendChar(StringBuilder sb, char ch, int cnt) {
        for (int i = 0; i < cnt; i++) {
            sb.append(ch);
        }
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
        testCase4();
        testCase5();
    }

    public static void testCase1() {
        int num = 3;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase2() {
        int num = 4;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase3() {
        int num = 9;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase4() {
        int num = 58;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }

    public static void testCase5() {
        int num = 1994;

        String result = new Solution().intToRoman(num);
        System.out.println(result);
    }
}

最长公共前缀

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

 

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
 

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

题目解答

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
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        String s0 = strs[0];
        for (int i = 0; i < s0.length(); i++) {
            for (int j = 1; j < strs.length; j++) {
                String s1 = strs[j];
                if (i >= s1.length() || s1.charAt(i) != s0.charAt(i)) {
                    return s0.substring(0, i);
                }
            }
        }

        return s0;
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
    }

    public static void testCase1() {
        String[] strs = { "flower", "flow", "flight" };

        String result = new Solution().longestCommonPrefix(strs);
        String expect = "fl";
        System.out.println(result);
        System.out.println(expect);
        System.out.println(result.equals(expect));
    }

    public static void testCase2() {
        String[] strs = { "dog", "racecar", "car" };

        String result = new Solution().longestCommonPrefix(strs);
        String expect = "";
        System.out.println(result);
        System.out.println(expect);
        System.out.println(result.equals(expect));
    }
}

反转字符串中的单词

题目描述

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

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

 

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"
示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
 

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
 

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

题目解答

  • 分割反转法：将字符串split成字符串数组，再对数组进行反转并join成新的字符串
  • 栈反转法：将字符串中的单词从左到后压入栈中，最后依次弹出单词加入到新的字符串中
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
public class Solution {
    public String reverseWords(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        Deque<String> d = new ArrayDeque<String>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
                // 将单词 push 到队列的头部
                d.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());

        return String.join(" ", d);
    }
}

N字形变换

题目描述

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
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 N 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);
 

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I
示例 3：

输入：s = "A", numRows = 1
输出："A"
 

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

题目解答

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
92
93
94
95
96
97
98
99
public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        } else if (s.length() <= numRows) {
            return s;
        }

        StringBuilder sb = new StringBuilder();

        int len = s.length();
        for (int i = 0; i < numRows; i++) {
            int j = i;
            if (j < len) {
                sb.append(s.charAt(j));
                if (sb.length() >= len) {
                    return sb.toString();
                }
            } else {
                break;
            }

            while (true) {
                // 从当前层到达底层再返回
                if (i != numRows - 1) {
                    // 从当前层到达底层再返回当前层需要移动的距离
                    int d = 2 * (numRows - 1 - i);
                    j = j + d;

                    if (j < len) {
                        sb.append(s.charAt(j));
                        if (sb.length() >= len) {
                            return sb.toString();
                        }
                    } else {
                        break;
                    }
                }

                // 从当前层到达顶层再返回
                if (i != 0) {
                    // 从当前层到达顶层再返回当前层需要移动的距离
                    int d = 2 * (i - 0);
                    j = j + d;

                    if (j < len && sb.length() < len) {
                        sb.append(s.charAt(j));
                        if (sb.length() >= len) {
                            return sb.toString();
                        }
                    } else {
                        break;
                    }
                }
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        testCase1();
        testCase2();
        testCase3();
    }

    public static void testCase1() {
        String s = "PAYPALISHIRING";
        int numRows = 3;

        String result = new Solution().convert(s, numRows);
        String expect = "PAHNAPLSIIGYIR";
        System.out.println(result);
        System.out.println(expect);
        System.out.println(result.equals(expect));
    }

    public static void testCase2() {
        String s = "PAYPALISHIRING";
        int numRows = 4;

        String result = new Solution().convert(s, numRows);
        String expect = "PINALSIGYAHRPI";
        System.out.println(result);
        System.out.println(expect);
        System.out.println(result.equals(expect));
    }

    public static void testCase3() {
        String s = "A";
        int numRows = 1;

        String result = new Solution().convert(s, numRows);
        String expect = "A";
        System.out.println(result);
        System.out.println(expect);
        System.out.println(result.equals(expect));
    }
}

困难

字符串匹配

题目描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

 

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

题目解答

1
//

TODO：字符串匹配

文本左右对齐

题目描述

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
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
 

示例 1:

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
示例 2:

输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]
 

提示:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] 由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth

题目解答

1
//

TODO：文本左右对齐

只想买包辣条