01.09. 字符串轮转
 字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（
 比如，waterbottle是erbottlewat旋转后的字符串）。

 示例1:
  输入：s1 = "waterbottle", s2 = "erbottlewat"
  输出：True
 
 示例2:
  输入：s1 = "aa", s2 = "aba"
  输出：False
 
 提示：
 字符串长度在[0, 100000]范围内。
 
 说明:
 你能只调用一次检查子串的方法吗？

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/string-rotation-lcci
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        if(s1.compare(s2) == 0) return true;
        if (s1 == "" || s2 == "") return false;
        if (s2.length() > s1.length()) return false;
        s1.append(s1);
        return s1.find(s2) != -1;
    }
};

242. 有效的字母异位词
 
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:
输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-anagram
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    bool isAnagram(string s, string t) {

        if (s.length() != t.length()) return false;
       
        vector<int> results(26);
       
        int length = (int)s.length();
        for (int i = 0; i<length; i++) {
            ++results[s[i]-'a'];
        }
        
        for (int i = 0; i<length; i++) {
            int val = --results[t[i]-'a'];
            if (val<0) return false;
        }

        return true;
    }
};

572. 另一个树的子树
 
 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

 示例 1:
 给定的树 s:

      3
     / \
    4   5
   / \
  1   2
 给定的树 t：

    4
   / \
  1   2
 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

 示例 2:
 给定的树 s：

      3
     / \
    4   5
   / \
  1   2
     /
    0
 给定的树 t：

    4
   / \
  1   2
 返回 false。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/subtree-of-another-tree
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == nullptr || t == nullptr) return false;
        
        string * s1 = new string();
        postorder(s1, s);
        
        string * s2 = new string();
        postorder(s2, t);

        return (int)s1->find(*s2) != -1;
    }
    
    void postorder(string* result, TreeNode* node){
        if (node == nullptr){
            result->append("#!");
            return;
        }
        postorder(result,node->left);
        postorder(result,node->right);
        //打印节点
        
        result->append(to_string(node->val));
        result->append("!");
    }
};

151. 翻转字符串里的单词				
 
 给定一个字符串，逐个翻转字符串中的每个单词。

 说明：
 无空格字符构成一个 单词 。
 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
  
 示例 1：
 输入："the sky is blue"
 输出："blue is sky the"
 
 示例 2：
 输入："  hello world!  "
 输出："world! hello"
 解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 
 示例 3：
 输入："a good   example"
 输出："example good a"
 解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 
 示例 4：
 输入：s = "  Bob    Loves  Alice   "
 输出："Alice Loves Bob"
 
 示例 5：
 输入：s = "Alice does not even like bob"
 输出："bob like even not does Alice"
  

 提示：
 1 <= s.length <= 104
 s 包含英文大小写字母、数字和空格 ' '
 s 中 至少存在一个 单词
  
 进阶：
 请尝试使用 O(1) 额外空间复杂度的原地解法。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/reverse-words-in-a-string
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    string reverseWords(string s) {
        if (s.length() == 0) return s;

        //1.消除多余的空格
        int curIdx = 0;//记录当前可以放置字符的位置
        bool preSpace = true;//上一个字符是否为空格(默认为true,相当于-1位置有个哨兵)
        int len = 0;
        int length = (int)s.length();
        for (int i = 0; i<length; i++) {
            if (s[i] != ' ') {
                s[curIdx++] = s[i];
                preSpace = false;
            }else if(preSpace == false){
                s[curIdx++] = s[i];
                preSpace = true;
            }
        }
        len = preSpace ? curIdx -1 : curIdx;
        
        
        //2.字符串整体反转
        reverseString(&s, 0, len);
        
        
        //3.反转每个单词
        int lIdx = -1;
        int rIdx;
        for (rIdx = 0; rIdx<len; rIdx++) {
            if (s[rIdx] == ' ') {
                reverseString(&s, lIdx+1, rIdx);
                lIdx = rIdx;
            }
        }
       
        reverseString(&s, lIdx+1, rIdx); //反转最后一个单词
        return s.substr(0,len);
    }
    
    
    /// 反转一个字符串
    /// @param str 字符串
    /// @param l 左闭右开[l r)
    /// @param r 左闭右开[l r)
    void reverseString(string* str,int l,int r){
        r--;
        while (l < r) {
            char temp = (*str)[l];
            (*str)[l] = (*str)[r];
            (*str)[r] = temp;
            l++;
            r--;
        }
    }
};

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

 示例 1:
 输入: "abcabcbb"
 输出: 3
 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 
 示例 2:
 输入: "bbbbb"
 输出: 1
 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 
 示例 3:
 输入: "pwwkew"
 输出: 3
 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution1 {
public:
    int lengthOfLongestSubstring(string s) {
       
        int len = (int)s.length();
        if (len == 0) return 0;

        //记录上一次出现的位置,默认初始化为-1
        map<int, int> preIdxs;
        for (int i = 0; i<len; i++) {
            preIdxs[s[i]] = -1;
        }
       
        //0号位置的值
        preIdxs[s[0]] = 0;
        
        //记录i-1位置最大子串的左边索引
        int li = 0;
        
        //最大子串的长度
        int maxLen = 1;
        
        for (int i = 1; i<len; i++) {
            //上次出现的索引
            int pi = preIdxs[s[i]];
            
//            if (pi < li) {
//                li = li;
//            }else if(pi == li){
//                li = pi + 1;
//            }else{
//                li = pi + 1;
//            }
            if (pi >= li) li = pi + 1;
            
            maxLen = max(maxLen, i-li+1);
            
            //更新本次出现的索引
            preIdxs[s[i]] = i;
        }
        
        return maxLen;
    }
};