Эта статья была впервые опубликована в моем личном блоге:племя хвост хвост
1. Алгоритм КМП
Говоря о проблеме со строками, я должен упомянуть алгоритм KMP, который используется для решения задачи поиска строки: он может найти позицию, в которой подстрока (W) встречается в строке (S). Алгоритм KMP уменьшает временную сложность сопоставления символов до O(m+n), а пространственную сложность составляет всего O(m). Поскольку метод «поиска грубой силой» будет многократно возвращаться к основной строке, что приводит к низкой эффективности, алгоритм KMP может использовать достоверную информацию, которая была частично сопоставлена, чтобы предотвратить возврат указателя в основной строке, и путем изменения указателя подстроки. , позвольте строке шаблона как можно больше переместиться в допустимое место.
Для получения подробной информации об алгоритме см.:
- Алгоритм сопоставления строк KMP
- Тщательно понять KMP от начала до конца
- Как лучше понять и освоить алгоритм КМП?
- Подробный анализ алгоритма KMP
- Графический алгоритм KMP
- Ван может понять алгоритм сопоставления строк KMP [двуязычные субтитры]
- Алгоритм сопоставления строк KMP 1
1.1 Алгоритм БМ
Алгоритм BM также является алгоритмом точного сопоставления строк.Он использует метод сравнения справа налево и применяет два эвристических правила, а именно правило плохого символа и правило хорошего суффикса, для определения расстояния перехода вправо. Основная идея состоит в том, чтобы выполнять сопоставление символов справа налево.После обнаружения несовпадающих символов найдите максимальное значение сдвига вправо из таблицы плохих символов и таблицы хороших суффиксов и переместите строку шаблона вправо, чтобы продолжить сопоставление.Алгоритм сопоставления строк KMP
2. Замените пробелы
Меч относится к предложению:заменить пробелыПожалуйста, реализуйте функцию, которая заменяет каждый пробел в строке на "%20". Например, если строка We Are Happy., замененная строка будет We%20Are%20Happy.
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer res = new StringBuffer();
int len = str.length() - 1;
for(int i = len; i >= 0; i--){
if(str.charAt(i) == ' ')
res.append("02%");
else
res.append(str.charAt(i));
}
return res.reverse().toString();
}
}
3. Самый длинный общий префикс
Leetcode: самый длинный общий префиксНапишите функцию для поиска самого длинного общего префикса в массиве строк. Если общего префикса не существует, возвращается пустая строка "".
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0)
return "";
Arrays.sort(strs);
char [] first = strs[0].toCharArray();
char [] last = strs[strs.length - 1].toCharArray();
StringBuffer res = new StringBuffer();
int len = first.length < last.length ? first.length : last.length;
int i = 0;
while(i < len){
if(first[i] == last[i]){
res.append(first[i]);
i++;
}
else
break;
}
return res.toString();
}
}
4. Самый длинный палиндром
LeetCode: самый длинный палиндромДана строка, содержащая прописные и строчные буквы, найти самый длинный палиндром, составленный из этих букв. Во время построения помните о чувствительности к регистру. Например, «Аа» нельзя рассматривать как палиндром.
class Solution {
public int longestPalindrome(String s) {
HashSet<Character> hs = new HashSet<>();
int len = s.length();
int count = 0;
if(len == 0)
return 0;
for(int i = 0; i<len; i++){
if(hs.contains(s.charAt(i))){
hs.remove(s.charAt(i));
count++;
}else{
hs.add(s.charAt(i));
}
}
return hs.isEmpty() ? count * 2 : count * 2 + 1;
}
}
4.1 Проверка палиндрома
Leetcode: палиндром проверкиУчитывая строку, убедитесь, что это палиндром, учитывая только буквенно-цифровые символы, игнорируя регистр букв. Объяснение: В этой задаче мы определяем пустую строку как допустимый палиндром.
Два указателя сравниваются голова к хвосту. Обратите внимание, что учитываются только буквенно-цифровые символы, а регистр букв можно не учитывать.
class Solution {
public boolean isPalindrome(String s) {
if(s.length() == 0)
return true;
int l = 0, r = s.length() - 1;
while(l < r){
if(!Character.isLetterOrDigit(s.charAt(l))){
l++;
}else if(!Character.isLetterOrDigit(s.charAt(r))){
r--;
}else{
if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
return false;
l++;
r--;
}
}
return true;
}
}
4.2 Самая длинная палиндромная подстрока
LeetCode: самая длинная палиндромная подстрокаДля заданной строки s найти самую длинную подстроку палиндрома в s. Вы можете предположить, что s имеет максимальную длину 1000.
class Solution {
private int index, len;
public String longestPalindrome(String s) {
if(s.length() < 2)
return s;
for(int i = 0; i < s.length()-1; i++){
PalindromeHelper(s, i, i);
PalindromeHelper(s, i, i+1);
}
return s.substring(index, index+len);
}
public void PalindromeHelper(String s, int l, int r){
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
if(len < r - l - 1){
index = l + 1;
len = r - l - 1;
}
}
}
4.3 Самая длинная палиндромная последовательность
LeetCode: самая длинная палиндромная подпоследовательностьДана строка s, найти в ней самую длинную палиндромную подпоследовательность. Можно предположить, что максимальная длина s равна 1000.Разница между самой длинной подпоследовательностью палиндрома и самой длинной подстрокой палиндрома в предыдущем вопросе заключается в том, что подстрока — это непрерывная последовательность в строке, а подпоследовательность — это последовательность символов в строке, сохраняющая относительное положение. Например, «bbbb " может составить подпоследовательность, но не подстроку строки "bbbab".
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int [][] dp = new int[len][len];
for(int i = len - 1; i>=0; i--){
dp[i][i] = 1;
for(int j = i+1; j < len; j++){
if(s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][len-1];
}
}
5. Расположение струн
Leetcode: расположение струнИмея две строки s1 и s2, напишите функцию, определяющую, содержит ли s2 перестановку s1. Другими словами, одна из перестановок первой строки является подстрокой второй строки.
class Solution {
public boolean checkInclusion(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
int [] count = new int [128];
if(l1 > l2)
return false;
for(int i = 0; i<l1; i++){
count[s1.charAt(i) - 'a']++;
count[s2.charAt(i) - 'a']--;
}
if(allZero(count))
return true;
for(int i = l1; i<l2; i++){
count[s2.charAt(i) - 'a']--;
count[s2.charAt(i-l1) - 'a']++;
if(allZero(count))
return true;
}
return false;
}
public boolean allZero(int [] count){
int l = count.length;
for(int i = 0; i < l; i++){
if(count[i] != 0)
return false;
}
return true;
}
}
6. Выведите полную перестановку строки
Меч относится к предложению:расположение струнВведите строку и распечатайте все перестановки символов в строке лексикографически. Например, если вводится строка abc, выводятся все строки abc, acb, bac, bca, cab и cba, которые могут быть упорядочены по символам a, b и c.
Разбейте проблему на простые шаги: Первый шаг — найти все символы, которые могут стоять в первой позиции (то есть поменять местами первый символ со всеми последующими символами [одинаковые символы не меняются местами]); Второй шаг — исправить первый символ и найти расположение всех следующих символов. В это время все следующие символы можно разделить на две части (первый символ и все остальные символы) и так далее. Таким образом, мы можем решить его рекурсивно.
public class Solution {
ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> Permutation(String str) {
if(str == null)
return res;
PermutationHelper(str.toCharArray(), 0);
Collections.sort(res);
return res;
}
public void PermutationHelper(char[] str, int i){
if(i == str.length - 1){
res.add(String.valueOf(str));
}else{
for(int j = i; j < str.length; j++){
if(j!=i && str[i] == str[j])
continue;
swap(str, i, j);
PermutationHelper(str, i+1);
swap(str, i, j);
}
}
}
public void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
}
7. Первый символ, который встречается только один раз
Предложение мечника:первый символ, который встречается только один разНайдите первый символ, который встречается в строке только один раз (0
Сначала подсчитайте количество вхождений каждой буквы в хеш-таблицу, а затем напрямую обратитесь к хэш-таблице, чтобы получить количество раз во втором сканировании. Массивы также можно использовать вместо хеш-таблиц.
import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
int len = str.length();
if(len == 0)
return -1;
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i < len; i++){
if(map.containsKey(str.charAt(i))){
int value = map.get(str.charAt(i));
map.put(str.charAt(i), value+1);
}else{
map.put(str.charAt(i), 1);
}
}
for(int i = 0; i < len; i++){
if(map.get(str.charAt(i)) == 1)
return i;
}
return -1;
}
}
8. Перевернуть столбец порядка слов
Предложение мечника:Перевернуть столбец порядка слов LeetCode: Перевернуть слова в строке
Это легко сделать с помощью trim() и split().
public class Solution {
public String reverseWords(String s) {
if(s.trim().length() == 0)
return s.trim();
String [] temp = s.trim().split(" +");
String res = "";
for(int i = temp.length - 1; i > 0; i--){
res += temp[i] + " ";
}
return res + temp[0];
}
}
9. Вращение строки
Leetcode: повернуть строкуДаны две строки, A и B. Операция поворота A состоит в том, чтобы переместить крайний левый символ A в крайний правый. Например, если A = 'abcde', результатом после одного хода будет 'bcdea'. Возвращает True, если A может стать B после нескольких операций вращения.
class Solution {
public boolean rotateString(String A, String B) {
return A.length() == B.length() && (A+A).contains(B);
}
}
9.1 Повернуть струну влево
Предложение мечника:Повернуть строку влевоНа ассемблере есть инструкция сдвига, называемая Rotate Left (ROL), и теперь есть простая задача смоделировать результат работы этой инструкции строкой. Для заданной последовательности символов S выведите последовательность после циклического сдвига влево на K бит. Например, последовательность символов S="abcXYZdef" требует вывода результата циклического сдвига влево на 3 бита, то есть "XYZdefabc". Разве это не просто? Хорошо, сделай это!
После n-го символа ножом будет разрезана строка, разделенная на две части, а затем снова соединенная. Обратите внимание на случай, когда длина строки равна 0.
public class Solution {
public String LeftRotateString(String str,int n) {
int len = str.length();
if(len == 0)
return "";
n = n % len;
String s1 = str.substring(n, len);
String s2 = str.substring(0, n);
return s1+s2;
}
}
9.2 Реверс струн
LeetCode: перевернуть строкуНапишите функцию, которая переворачивает входную строку.
class Solution {
public String reverseString(String s) {
if(s.length() < 2)
return s;
int l = 0, r = s.length() - 1;
char [] strs = s.toCharArray();
while(l < r){
char temp = strs[l];
strs[l] = strs[r];
strs[r] = temp;
l++;
r--;
}
return new String(strs);
}
}
10. Преобразование строки в целое число
Предложение мечника:преобразовать строку в целое числоПреобразование строки в целое число (реализуйте функцию Integer.valueOf(string), но возвращайте 0, если строка не соответствует требованиям чисел), требует, чтобы вы не могли использовать библиотечную функцию, которая преобразует целые числа из строк. Возвращает 0, если значение равно 0 или если строка не является допустимым значением.
public class Solution {
public int StrToInt(String str) {
if(str.length() == 0)
return 0;
int flag = 0;
if(str.charAt(0) == '+')
flag = 1;
else if(str.charAt(0) == '-')
flag = 2;
int start = flag > 0 ? 1 : 0;
long res = 0;
while(start < str.length()){
if(str.charAt(start) > '9' || str.charAt(start) < '0')
return 0;
res = res * 10 + (str.charAt(start) - '0');
start ++;
}
return flag == 2 ? -(int)res : (int)res;
}
}
11. Сопоставление регулярных выражений
Меч относится к предложению:соответствие регулярному выражениюПожалуйста, реализуйте функцию для сопоставления регулярных выражений, включая '.' и '*'. Символ '.' в шаблоне означает любой символ, а '*' означает, что предшествующий ему символ может встречаться любое количество раз (включая 0). В этом вопросе совпадение означает, что все символы строки соответствуют всему шаблону. Например, строка "aaa" соответствует шаблонам "a.a" и "ab*ac*a", но ни "aa.a", ни "ab*a"
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int j = 0; i < p.length(); j++) {
if (p.charAt(j) == '*' && dp[0][j-1]) {
dp[0][j+1] = true;
}
}
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return dp[s.length()][p.length()];
}
12. Строки, представляющие числовые значения
Предложение мечника:строка, представляющая числовое значениеРеализуйте функцию, определяющую, представляет ли строка числовое значение (включая целые числа и десятичные дроби). Например, строки «+100», «5e2», «-123», «3,1416» и «-1E-16» представляют числовые значения. Но ни "12е", ни "1а3.14", ни "1.2.3", ни "+-5", ни "12е+4.3".
Установите три флажка, чтобы записать, появились ли «+/-», «e/E» и «.».
public class Solution {
public boolean isNumeric(char[] str) {
int len = str.length;
boolean sign = false, decimal = false, hasE = false;
for(int i = 0; i < len; i++){
if(str[i] == '+' || str[i] == '-'){
if(!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E')
return false;
if(sign && str[i-1] != 'e' && str[i-1] != 'E')
return false;
sign = true;
}else if(str[i] == 'e' || str[i] == 'E'){
if(i == len - 1)
return false;
if(hasE)
return false;
hasE = true;
}else if(str[i] == '.'){
if(hasE || decimal)
return false;
decimal = true;
}else if(str[i] < '0' || str[i] > '9')
return false;
}
return true;
}
}
13. Первый уникальный символ в потоке символов
Предложение мечника:Первый уникальный символ в потоке символовПожалуйста, реализуйте функцию для поиска первого единичного символа в потоке символов. Например, когда из потока символов считываются только первые два символа «go», первым символом, который встречается только один раз, является «g». При чтении первых шести символов «google» из этого потока символов первый символ, который встречается только один раз, — «l».
Хеш-таблица используется для хранения каждого символа и количества его вхождений, а строка s используется для хранения порядка символов в потоке символов.
import java.util.HashMap;
public class Solution {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
StringBuffer s = new StringBuffer();
//Insert one char from stringstream
public void Insert(char ch)
{
s.append(ch);
if(map.containsKey(ch)){
map.put(ch, map.get(ch)+1);
}else{
map.put(ch, 1);
}
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce()
{
for(int i = 0; i < s.length(); i++){
if(map.get(s.charAt(i)) == 1)
return s.charAt(i);
}
return '#';
}
}