@@ -464,17 +464,14 @@ public String addStrings(String num1, String num2) {
464464[ 实现 strStr()] ( https://leetcode-cn.com/problems/implement-strstr/ )
465465
466466``` java
467- // 思路一:暴力解法
468- // 按位置去匹配,如果不合适,就移到下一位
469-
470467public int strStr(String haystack, String needle) {
471- if (needle== null || needle. length()== 0 ){
472- return - 1 ;
473- }
474-
475468 int m= haystack. length();
476469 int n= needle. length();
477470
471+ if (n== 0 ){ // needle 是空字符串,默认返回 0
472+ return 0 ;
473+ }
474+
478475 int i= 0 ,j= 0 ;
479476 int k= 0 ;
480477 while (i< m && j< n){
@@ -486,62 +483,11 @@ public int strStr(String haystack, String needle) {
486483 i= ++ k;
487484 }
488485 }
489- if (j== n){
486+ if (j== n){ // 说明 needle 完全匹配
490487 return k;
491488 }
492-
493- return - 1 ;
494- }
495- ```
496-
497-
498-
499- ``` java
500- // 思路二 :KMP 算法
501-
502- public int strStr(String haystack, String needle) {
503- if (needle== null || needle. length()== 0 ){
504- return 0 ;
505- }
506- int [] next= getNext(needle);
507- int i= 0 ,j= 0 ;
508- while (i< haystack. length() && j< needle. length()){
509- if (j== - 1 || haystack. charAt(i)== needle. charAt(j)){
510- i++ ;
511- j++ ;
512- }else {
513- j= next[j];
514- }
515- }
516- // 说明模板串是待匹配串的子串
517- if (j== needle. length()){
518- // 返回的是待匹配串的下标
519- return i- needle. length();
520- }
521489 return - 1 ;
522490}
523-
524- // 获取 next 数组
525- // next[j]的值(也就是t)表示,
526- // 当P[j] != T[i]时,j 指针的下一步要移动到的位置(其中P是模式串,T是主串)。
527-
528- private int [] getNext(String needle) {
529- int [] next= new int [needle. length()];
530- int j= 0 ,t= - 1 ;
531- next[0 ]= - 1 ;
532- while (j< needle. length()- 1 ){
533- if (t== - 1 || needle. charAt(j)== needle. charAt(t)){
534- // needle.charAt(j): 表示后缀的单个字符
535- // needle.charAt(t): 表示前缀的单个字符
536- next[j+ 1 ]= t+ 1 ;
537- t++ ;
538- j++ ;
539- }else {
540- t= next[t];
541- }
542- }
543- return next;
544- }
545491```
546492
547493
@@ -551,7 +497,32 @@ private int[] getNext(String needle) {
551497[ 最长回文串] ( https://leetcode-cn.com/problems/longest-palindrome/ )
552498
553499``` java
500+ // 思路:
501+ // 构成回文串的两种情况:
502+ // 1.字符出现次数为双数的组合
503+ // 2.字符出现次数为双数的组合+一个字符
504+
505+ public int longestPalindrome(String s) {
506+ if (s. length()== 1 ){
507+ return 1 ;
508+ }
509+ // 统计成对出现的字符次数
510+ int cnt= 0 ;
511+ // set 不会存储相同的字符
512+ Set<Character > set= new HashSet<> ();
513+
514+ for (int i= 0 ;i< s. length();i++ ){
515+ char c= s. charAt(i);
516+ if (! set. contains(c)){
517+ set. add(c);
518+ }else { // 说明 c 成对出现
519+ set. remove((Character ) c);
520+ cnt++ ;
521+ }
522+ }
554523
524+ return (set. isEmpty()? (2 * cnt): (2 * cnt+ 1 ));
525+ }
555526```
556527
557528
@@ -561,7 +532,26 @@ private int[] getNext(String needle) {
561532[ 最长回文子序列] ( https://leetcode-cn.com/problems/longest-palindromic-subsequence/ )
562533
563534``` java
564-
535+ public int longestPalindromeSubseq(String s) {
536+ int n= s. length();
537+ if (n<= 1 ){
538+ return n;
539+ }
540+
541+ // dp[i][j] 表示 s[i,j] 之间最长的回文子序列的长度
542+ int [][] dp= new int [n][n];
543+ for (int i= n- 1 ;i>= 0 ;i-- ){
544+ dp[i][i]= 1 ; // TODO:只有一个元素,最长回文子序列的长度为 1
545+ for (int j= i+ 1 ;j< n;j++ ){ // j 从 j+1 开始
546+ if (s. charAt(i)== s. charAt(j)){
547+ dp[i][j]= dp[i+ 1 ][j- 1 ]+ 2 ;
548+ }else {
549+ dp[i][j]= Math . max(dp[i+ 1 ][j],dp[i][j- 1 ]);
550+ }
551+ }
552+ }
553+ return dp[0 ][n- 1 ];
554+ }
565555```
566556
567557
0 commit comments