几个字符串相关的题目，来自LeetCode和LintCode

本文主要是介绍几个字符串相关的题目，来自LeetCode和LintCode，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个是Leetcode上关于字符串的题目，要求实现一个 strstr 函数，搜寻子串在源字符串中的位置，如果没有在源字符串中则返回 -1.

链接如下：
https://leetcode.com/problems/implement-strstr/

C++实现如下：

class Solution {
public:int strStr(string haystack, string needle) {if (haystack.empty() && needle.empty()) return 0;if (haystack.empty()) return -1;if (needle.empty()) return 0;// in case of overflow for negativeif (haystack.size() < needle.size()) return -1;for (int i = 0; i < haystack.size() - needle.size() + 1; i++) {string::size_type j = 0;for (; j < needle.size(); j++) {if (haystack[i + j] != needle[j]) break;}if (j == needle.size()) return i;}return -1;}
};

这是基于双 for 循环的判定算法，更高效的算法是 KMP 算法。
细节：

for (int i = 0; i < haystack.size() - needle.size() + 1; i++)

这处循环除去了目标字符串长度大于剩余源字符串长度的情况，更好的细节写法可以将 haystack.size() - needle.size() + 1 这个表达式赋值一个变量，在 for 的初始化语句中，不必每次比较都要运算一遍。

KMP 算法的日后再补充

=====================================
这个是LintCode上判断一个字符串是否为另外一个字符串经过混淆顺序得到的。
判断两个字符串是否互为变位词，若区分大小写，考虑空白字符时，直接来理解可以认为两个字符串的拥有各不同字符的数量相同。对于比较字符数量的问题常用的方法为遍历两个字符串，统计其中各字符出现的频次，若不等则返回false. 有很多简单字符串类面试题都是此题的变形题。
其C++实现如下：

class Solution {
public:/*** @param s: The first string* @param b: The second string* @return true or false*/bool anagram(string s, string t) {if (s.empty() || t.empty()) {return false;}if (s.size() != t.size()) {return false;}int letterCount[256] = {0};for (int i = 0; i != s.size(); ++i) {++letterCount[s[i]];--letterCount[t[i]];}for (int i = 0; i != t.size(); ++i) {if (letterCount[t[i]] != 0) {return false;}}return true;}
};

链接如下：
http://www.lintcode.com/en/problem/two-strings-are-anagrams/

=================================
这是上一道题目的变形，判断 B 中的所有字符是否在 A 中存在。依旧是 ++ – ，只不过稍稍变形，发现缺少一个字符立马返回 false

class Solution {
public:bool compareStrings(string A, string B) {// write your code hereif (A.size() < B.size) return false;const int alphanum = 26;int letterCount[alphanum] = {0};for (int i = 0; i < A.size(); ++i) {++letterCount[A[i] - 'A'];}for (int i = 0; i < B.size(); ++i) {--letterCount[B[i] - 'A'];if (letterCount[B[i] - 'A'] < 0) return false;}return true;}
};

===================================

class Solution {
public:/*** @param strs: A list of strings* @return: A list of strings*/vector<string> anagrams(vector<string> &strs) {if (strs.size() < 2) {return strs;}vector<string> result;vector<bool> visited(strs.size(), false);for (int s1 = 0; s1 != strs.size(); ++s1) {bool has_anagrams = false;for (int s2 = s1 + 1; s2 < strs.size(); ++s2) {if ((!visited[s2]) && isAnagrams(strs[s1], strs[s2])) {result.push_back(strs[s2]);visited[s2] = true;has_anagrams = true;}}if ((!visited[s1]) && has_anagrams) result.push_back(strs[s1]);}return result;}private:bool isAnagrams(string &s, string &t) {if (s.size() != t.size()) {return false;}const int AlphabetNum = 26;int letterCount[AlphabetNum] = {0};for (int i = 0; i != s.size(); ++i) {++letterCount[s[i] - 'a'];--letterCount[t[i] - 'a'];}for (int i = 0; i != t.size(); ++i) {if (letterCount[t[i] - 'a'] < 0) {return false;}}return true;}
};

class Solution {
public:/*** @param strs: A list of strings* @return: A list of strings*/vector<string> anagrams(vector<string> &strs) {unordered_map<string, int> hash;for (int i = 0; i < strs.size(); i++) {string str = strs[i];sort(str.begin(), str.end());++hash[str];}vector<string> result;for (int i = 0; i < strs.size(); i++) {string str = strs[i];sort(str.begin(), str.end());if (hash[str] > 1) {result.push_back(strs[i]);}}return result;}
};