算法3---字符串

字符串没有什么很重要的知识点需要说的，但是还是有一些比较重要的题，我们来一起分享一下

1 Valid Palindrome

描述：

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring

cases.

For example,

”A man, a plan, a canal: Panama” is a palindrome.

”race a car” is not a palindrome.

Note: Have you consider that the string might be empty? �is is a good question to ask during an

interview.

For the purpose of this problem, we define empty string as valid palindrome.

解决方法：

 1 bool isPalindrome(string s)
 2 {
 3     transform(s.begin(), s.end(), s.begin(), ::tolower);
 4     auto left = s.begin(), right = prev(s.end());
 5     while (left < right)
 6      {
 7     if (!::isalnum(*left)) ++left;
 8     else if (!::isalnum(*right)) --right;
 9     else if (*left != *right) return false;
10     }
11     return true;
12 }

当然在这里面用到了一些库函数，使用#include <string>就可以直接用，对于上面的transform函数，我们再这里详细讲解一下

transform函数的作用是：将某操作应用于指定范围的每个元素。transform函数有两个重载版本：

transform(first,last,result,op);//first是容器的首迭代器，last为容器的末迭代器，result为存放结果的容器，op为要进行操作的一元函数对象或sturct、class

transform(first1,last1,first2,result,binary_op);//first1是第一个容器的首迭代器，last1为第一个容器的末迭代器，first2为第二个容器的首迭代器，result为存放结果的容器，binary_op为要进行操作的二元函数对象或sturct 、class。

具体使用具体如下

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 char op(char ch)
 5 {
 6     if(ch>='A'&&ch<='Z')
 7         return ch+32;
 8     else
 9         return ch;
10 }
11 int main()
12 {
13     string first,second;
14     cin>>first;
15     second.resize(first.size());
16     transform(first.begin(),first.end(),second.begin(),op);
17     cout<<second<<endl;
18     return 0;
19 }

2 Implement strStr()

描述

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

分析

暴力算法的复杂度是 O(m ∗ n)，代码如下。更高效的的算法有 KMP 算法、 Boyer-Mooer 算法和

Rabin-Karp 算法。面试中暴力算法足够了，一定要写得没有 BUG。

 1 #include <iostream>
 2 
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 int strStr(string hack, string need);
 8 
 9 int main()
10 {
11     string hack="hellotiisosk";
12     string need="tii";
13     int m=strStr(hack,need);
14     if (m==-1)
15     {
16         cout<<"can't find it!"<<endl;
17     }
18     else
19         cout<<"find it and the position is "<<m<<endl;
20 
21     return 0;
22 }
23 
24  int strStr(string hack, string need)
25  {
26     int needlen = need.size();
27     int hacklen = hack.size();
28     //cout<<needlen<<endl;
29     //cout<<hacklen<<endl;
30     if (needlen == 0)
31         return 0;
32     if (needlen == 0 && hacklen == 0 || needlen > hacklen)
33         return -1;
34     int i = 0;
35     while(i < hacklen-needlen)
36     {
37         //cout<<hacklen-needlen<<endl;
38         string cp=hack.substr(i,needlen);
39         //cout<<cp<<endl;
40         //cout<<strcmp(need,cp)<<endl;
41         if (need==cp)
42         {
43             return i+1;
44         }
45         i++;
46     }
47     return -1;
48 }