算法day08-字符串篇（2）

目录

• 反转字符串中的单词
  
• 找出字符串中第一个匹配项的下标
  
• 重复的子字符串
  

一、反转字符串中的单词

 　　主要思路：把整个字符串的头尾的空格先去掉，然后根据” ”来划分字符串数组，将字符串倒着放进结果中。

1. class Solution {
2.     public String reverseWords(String s) {
3.         String[] parts = s.trim().split("\\s+");        //去掉首尾空格
4.         StringBuilder sb = new StringBuilder();
5.         for(int i = parts.length-1; i>=0; i--){
6.             if(i == 0){
7.                 sb.append(parts[i]);
8.             }else{
9.                 sb.append(parts[i]);
10.                 sb.append(" ");
11.             }
12.         }
13.         return sb.toString();
14.     }
15. }
16. //时间复杂度：O(n)
17. //空间复杂度：O(n)

复制代码

 
二、右旋转字符串

 

1. class Main{
2.     public static void main(String[] args){
3.         Scanner in = new Scanner(System.in);
4.         int n = in.nextInt();
5.         in.nextLine();
6.         String s = in.nextLine();
7.         int p1 = s.length() - n;        //要右旋的起点
8.         int p2 = 0;
9.         StringBuilder sb = new StringBuilder();
10.         while(p1 < s.length()){
11.             sb.append(s.charAt(p1));
12.             p1++;
13.         }
14.         while(p2 < s.length() - n){
15.             sb.append(s.charAt(p2));
16.             p2++;
17.         }
18.         System.out.print(sb);
19.     }
20. }
21. //时间复杂度：O(N)
22. //空间复杂度：O(N)

复制代码

 
三、找出字符串中第一个匹配项的下标

 　　主要思路：在原字符串的每一个位置都截取一段子字符串来判断是否和needle相等。

1. class Solution {
2.     public int strStr(String haystack, String needle) {
3.         if(needle.length()==0){
4.             return 0;
5.         }
6.         if(needle.length() > haystack.length()){
7.             return -1;
8.         }
9.         for(int i=0; i<=haystack.length() - needle.length(); i++){
10.             if(haystack.substring(i, i+needle.length()).equals(needle)){
11.                 return i;
12.             }
13.         }
14.         return -1;
15.     }
16. }
17. //时间复杂度：O((n-m+1)*m)
18. //空间复杂度：O(1)

复制代码

// 时间复杂度：O(n)，其中 n 是字符串的长度，KMP 构造 next 数组只需要一次线性扫描。
// 空间复杂度：O(n)，用于存储前缀表 next[]。
 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！