字符串：基础

0014. 最长公共前缀 (opens new window)

题目

编写一个函数来查找字符串数组中的最长公共前缀。

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

示例 1：

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

示例 2：

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

提示：

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

解析

纵向扫描，以字符串数组中的第一个字符串为基准，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0][i];
            for (int j = 1; j < strs.size(); j++) {
                if (i == strs[j].length() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }
        return strs[0];
    }
};

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	for i := 0; i < len(strs[0]); i++ {
		c := strs[0][i]
		for j := 1; j < len(strs); j++ {
			if i == len(strs[j]) || strs[j][i] != c {
				return strs[0][:i]
			}
		}
	}
	return strs[0]
}

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        for i in range(len(strs[0])):
            c = strs[0][i]
            for j in range(1, len(strs)):
                if i == len(strs[j]) or strs[j][i] != c:
                    return strs[0][:i]
        return strs[0]

0151. 翻转字符串里的单词 (opens new window)

题目

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

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

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

• 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
• 翻转后单词间应当仅用一个空格分隔。
• 翻转后的字符串中不应包含额外的空格。

解析

先把字符串按照空格分隔成每个小单词，然后把单词前后翻转，最后再把每个单词中间添加空格。

代码

func reverseWords(s string) string {
	ss := strings.Fields(s)
	reverse(&ss, 0, len(ss)-1)
	return strings.Join(ss, " ")
}

func reverse(s *[]string, i int, j int) {
	for i < j {
		(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
		i++
		j--
	}
}

0161. 相隔为 1 的编辑距离 (opens new window)

题目

给定两个字符串 s 和 t，判断他们的编辑距离是否为 1。

满足编辑距离等于 1 有三种可能的情形：

1. 往 s 中插入一个字符得到 t
2. 从 s 中删除一个字符得到 t
3. 在 s 中替换一个字符得到 t

解析

同时遍历两个字符串，当遇到第一个不等的字符时，判断从该位置截取后的字符串是否相等。

代码

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int sl = s.length(), tl = t.length();
        if (sl > tl) {
            return isOneEditDistance(t, s);
        }
        for (int i = 0; i < sl; i++) {
            if (s[i] != t[i]) {
                if (sl == tl) {
                    return s.substr(i + 1) == t.substr(i + 1);
                } else {
                    return s.substr(i) == t.substr(i + 1);
                }
            }
        }
        return tl - sl == 1;
    }
};

func isOneEditDistance(s string, t string) bool {
	sl, tl := len(s), len(t)
	if sl > tl {
		return isOneEditDistance(t, s)
	}
	for i := 0; i < sl; i++ {
		if s[i] != t[i] {
			if sl == tl {
				return s[i+1:] == t[i+1:]
			} else {
				return s[i:] == t[i+1:]
			}
		}
	}
	return tl-sl == 1
}

0165. 比较版本号 (opens new window)

题目

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

• 如果 version1 > version2 返回 1，
• 如果 version1 < version2 返回 -1，
• 除此之外返回 0。

解析

为了降低复杂度，这里不适用 split 函数对字符串分割，而是手动逐位对比。

代码

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int len1 = version1.length();
        int len2 = version2.length();
        
        for (int p1 = 0, p2 = 0; p1 < len1 || p2 < len2; p1++, p2++) {
            int num1 = 0, num2 = 0;
            while (p1 < len1 && version1[p1] != '.') {
                num1 = num1 * 10 + version1[p1] - '0';
                p1++;
            }
            while (p2 < len2 && version2[p2] != '.') {
                num2 = num2 * 10 + version2[p2] - '0';
                p2++;
            }
            if (num1 != num2) {
                return num1 > num2 ? 1 : -1;
            }
        }
        return 0;
    }
};

func compareVersion(version1 string, version2 string) int {
	len1, len2 := len(version1), len(version2)
	for p1, p2 := 0, 0; p1 < len1 || p2 < len2; p1, p2 = p1+1, p2+1 {
		num1, num2 := 0, 0
		for p1 < len1 && version1[p1] != '.' {
			num1 = num1*10 + int(version1[p1]-'0')
			p1++
		}
		for p2 < len2 && version2[p2] != '.' {
			num2 = num2*10 + int(version2[p2]-'0')
			p2++
		}
		if num1 < num2 {
			return -1
		} else if num1 > num2 {
			return 1
		}
	}
	return 0
}

0168. Excel表列名称 (opens new window)

题目

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

解析

关键思路：使用 % 和 /= 进行进制转换。

代码

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string ans = "";
        while (columnNumber--) {
            ans = string(1, 'A' + columnNumber % 26) + ans;
            columnNumber /= 26;
        }
        return ans;
    }
};

func convertToTitle(columnNumber int) string {
	var ans []byte
	for columnNumber > 0 {
		columnNumber--
		ans = append([]byte{byte('A' + columnNumber%26)}, ans...)
		columnNumber /= 26
	}
	return string(ans)
}

0171. Excel表列序号 (opens new window)

题目

给你一个字符串 columnTitle ，表示 Excel 表格中的列名称。返回该列名称对应的列序号。

例如：

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

解析

本题是 0168. Excel表列名称 的逆运算，将 26 进制转换成十进制。

代码

class Solution {
public:
    int titleToNumber(string columnTitle) {
        int ans = 0;
        for (int i = 0; i < columnTitle.length(); i++) {
            ans = ans * 26 + (columnTitle[i] - 'A' + 1);
        }
        return ans;
    }
};

func titleToNumber(columnTitle string) int {
	ans := 0
	for i := 0; i < len(columnTitle); i++ {
		ans = ans*26 + int(columnTitle[i]-'A'+1)
	}
	return ans
}

0186. 翻转字符串里的单词 II (opens new window)

题目

给定一个字符串，逐个翻转字符串中的每个单词。

解析

先翻转整个字符串，然后返回每个词。

代码

class Solution {
public:
    void reverseWords(vector<char>& s) {
        reverse(s.begin(), s.end());
        for (int i = 0, j = 0; i < s.size(); i = ++j) {
            while (j < s.size() && s[j] != ' ') {
                j++;
            }
            reverse(s.begin() + i, s.begin() + j);
        }
    }
};

func reverseWords(s []byte) {
	reverse(&s, 0, len(s)-1)
	for i, j := 0, 0; i < len(s); i, j = j+1, j+1 {
		for j < len(s) && s[j] != ' ' {
			j++
		}
		reverse(&s, i, j-1)
	}
}

func reverse(s *[]byte, i int, j int) {
	for i < j {
		(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
		i++
		j--
	}
}

0344. 反转字符串 (opens new window)

题目

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

解析

首尾双指针依次交换。

代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            swap(s[left++], s[right--]);
        }
    }
};

func reverseString(s []byte) {
	left, right := 0, len(s)-1
	for left < right {
		s[left], s[right] = s[right], s[left]
		left++
		right--
	}
}

0345. 反转字符串中的元音字母 (opens new window)

题目

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。

解析

首尾双指针将元音字母依次交换。

代码

class Solution {
public:
    string reverseVowels(string s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !isVowel(s[left])) left++;
            while (left < right && !isVowel(s[right])) right--;
            swap(s[left++], s[right--]);
        }
        return s;
    }

    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
               c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
    }
};

func reverseVowels(s string) string {
	ss := []byte(s)
	left, right := 0, len(ss)-1
	for left < right {
		for left < right && !isVowel(ss[left]) {
			left++
		}
		for left < right && !isVowel(ss[right]) {
			right--
		}
		ss[left], ss[right] = ss[right], ss[left]
		left++
		right--
	}
	return string(ss)
}

func isVowel(c byte) bool {
	return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
		c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U'
}

0434. 字符串中的单词数 (opens new window)

题目

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

解析

• 方法一：将字符串按空格拆分后统计，空间复杂度 $O(n)$；
• 方法二：统计新单词出现的起始位置，空间复杂度 $O(1)$。

代码

class Solution {
public:
    int countSegments(string s) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != ' ' && (i == 0 || s[i - 1] == ' ')) {
                ans++;
            }
        }
        return ans;
    }
};

func countSegments(s string) int {
    return len(strings.Fields(s))
}

0482. 密钥格式化 (opens new window)

题目

有一个密钥字符串 S ，只包含字母，数字以及 '-'（破折号）。其中， N 个 '-' 将字符串分成了 N+1 组。

给你一个数字 K，请你重新格式化字符串，使每个分组恰好包含 K 个字符。特别地，第一个分组包含的字符个数必须小于等于 K，但至少要包含 1 个字符。两个分组之间需要用 '-'（破折号）隔开，并且将所有的小写字母转换为大写字母。

给定非空字符串 S 和数字 K，按照上面描述的规则进行格式化。

解析

由于第一组字符串个数不确定，因此从后向前遍历，最后将字符串翻转即可。

需要注意的是，可以通过当前字符串的长度，来决定是否要添加 '-' 字符。

代码

class Solution {
public:
    string licenseKeyFormatting(string s, int k) {
        string ans = "";
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s[i] == '-') {
                continue;
            }
            ans += ans.length() % (k + 1) == k ? "-" : "";
            ans += toupper(s[i]);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

func licenseKeyFormatting(s string, k int) string {
	var ans []byte
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] == '-' {
			continue
		}
		if len(ans)%(k+1) == k {
			ans = append(ans, '-')
		}
		c := s[i]
		if 'a' <= c && c <= 'z' {
			c -= 'a' - 'A'
		}
		ans = append(ans, c)
	}
	reverse(&ans, 0, len(ans)-1)
	return string(ans)
}

func reverse(s *[]byte, i int, j int) {
	for i < j {
		(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
		i++
		j--
	}
}

0521. 最长特殊序列 Ⅰ (opens new window)

题目

给你两个字符串，请你从这两个字符串中找出最长的特殊序列。

「最长特殊序列」定义如下：该序列为某字符串独有的最长子序列（即不能是其他字符串的子序列）。

子序列 可以通过删去字符串中的某些字符实现，但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列，任何字符串为其自身的子序列。

输入为两个字符串，输出最长特殊序列的长度。如果不存在，则返回 -1。

解析

• 如果两字符串相同，没有特殊子序列，返回 -1；
• 否则返回较长的字符串的长度。

代码

class Solution {
public:
    int findLUSlength(string a, string b) {
        if (a == b) {
            return -1;
        }
        return max(a.length(), b.length());
    }
};

func findLUSlength(a string, b string) int {
	if a == b {
		return -1
	} else if len(a) >= len(b) {
		return len(a)
	} else {
		return len(b)
	}
}

0541. 反转字符串 II (opens new window)

题目

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

解析

反转每个下标从 2k 的倍数开始的，长度为 k 的子串；若该子串长度不足 k，则反转整个子串。

代码

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.length();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};

func reverseStr(s string, k int) string {
	ans, n := []byte(s), len(s)
	for i := 0; i < n; i += 2 * k {
		if i+k < n {
			reverse(&ans, i, i+k-1)
		} else {
			reverse(&ans, i, n-1)
		}
	}
	return string(ans)
}

func reverse(s *[]byte, i int, j int) {
	for i < j {
		(*s)[i], (*s)[j] = (*s)[j], (*s)[i]
		i++
		j--
	}
}

0556. 下一个更大元素 III (opens new window)

题目

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

解析

1. 从后向前找到第一个升序的数字 num1；
2. 从后向前找到第一个比 num1 大的数字 num2；
3. 交换 num1 和 num2；
4. 将交换后 num2 后面的数字逆序（结果为升序排列，即下一个更大元素）。

代码

class Solution {
public:
    int nextGreaterElement(int n) {
        string s = to_string(n);

        // 找到第一个升序的数字
        int i = s.length() - 2;
        while (i >= 0 && s[i] >= s[i + 1]) i--;
        if (i < 0) return -1;

        // 找到交换的数字
        int j = s.length() - 1;
        while (j && s[j] <= s[i]) j--;

		// 交换并翻转后面的数字
        swap(s[i], s[j]);
        reverse(s.begin() + i + 1, s.end());

        long long num = stoll(s);
        return num > INT_MAX ? -1 : int(num);
    }
};

0557. 反转字符串中的单词 III (opens new window)

题目

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

解析

找到空格拆分的每个单词，全部反转即可。

代码

class Solution {
public:
    string reverseWords(string s) {
        int n = s.length();
        int left = 0, right = 0;
        while (right < n) {
            while (right < n && s[right] != ' ') right++;
            reverse(s.begin() + left, s.begin() + right);
            left = ++right;
        }
        return s;
    }
};

func reverseWords(s string) string {
	ss := strings.Fields(s)
	for i, word := range ss {
		ss[i] = reverse(word)
	}
	return strings.Join(ss, " ")
}

func reverse(s string) string {
	bytes := []byte(s)
	i, j := 0, len(bytes)-1
	for i < j {
		bytes[i], bytes[j] = bytes[j], bytes[i]
		i++
		j--
	}
	return string(bytes)
}