chapString.tex

\chapter{字符串}


\section{Valid Palindrome} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:valid-palindrome}


\subsubsection{描述}
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,\\
\code{"A man, a plan, a canal: Panama"} is a palindrome.\\
\code{"race a car"} is not a palindrome.

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

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


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
// Leet Code, Valid Palindrome
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    bool isPalindrome(string s) {
        transform(s.begin(), s.end(), s.begin(), ::tolower);
        auto left = s.begin(), right = prev(s.end());
        while (left < right) {
            if (!::isalnum(*left))  ++left;
            else if (!::isalnum(*right)) --right;
            else if (*left != *right) return false;
            else { left++, right--; }
        }
        return true;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Palindrome Number, 见 \S \ref{sec:palindrome-number}
\myenddot


\section{Implement strStr()} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:strstr}


\subsubsection{描述}
Implement strStr().

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


\subsubsection{分析}
暴力算法的复杂度是 $O(m*n)$，代码如下。更高效的的算法有KMP算法、Boyer-Mooer算法和Rabin-Karp算法。面试中暴力算法足够了，一定要写得没有BUG。


\subsubsection{暴力匹配}
\begin{Code}
// LeetCode, Implement strStr()
// 暴力解法，时间复杂度O(N*M)，空间复杂度O(1)
class Solution {
public:
    int strStr(const string& haystack, const string& needle) {
        if (needle.empty()) return 0;

        const int N = haystack.size() - needle.size() + 1;
        for (int i = 0; i < N; i++) {
            int j = i;
            int k = 0;
            while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]) {
                j++;
                k++;
            }
            if (k == needle.size()) return i;
        }
        return -1;
    }
};
\end{Code}


\subsubsection{KMP}
\begin{Code}
// LeetCode, Implement strStr()
// KMP，时间复杂度O(N+M)，空间复杂度O(M)
class Solution {
public:
    int strStr(const string& haystack, const string& needle) {
        return kmp(haystack.c_str(), needle.c_str());
    }
private:
    /*
     * @brief 计算部分匹配表，即next数组.
     *
     * @param[in] pattern 模式串
     * @param[out] next next数组
     * @return 无
     */
    static void compute_prefix(const char *pattern, int next[]) {
        int i;
        int j = -1;
        const int m = strlen(pattern);

        next[0] = j;
        for (i = 1; i < m; i++) {
            while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];

            if (pattern[i] == pattern[j + 1]) j++;
            next[i] = j;
        }
    }

    /*
     * @brief KMP算法.
     *
     * @param[in] text 文本
     * @param[in] pattern 模式串
     * @return 成功则返回第一次匹配的位置，失败则返回-1
     */
    static int kmp(const char *text, const char *pattern) {
        int i;
        int j = -1;
        const int n = strlen(text);
        const int m = strlen(pattern);
        if (n == 0 && m == 0) return 0; /* "","" */
        if (m == 0) return 0;  /* "a","" */
        int *next = (int*)malloc(sizeof(int) * m);

        compute_prefix(pattern, next);

        for (i = 0; i < n; i++) {
            while (j > -1 && pattern[j + 1] != text[i]) j = next[j];

            if (text[i] == pattern[j + 1]) j++;
            if (j == m - 1) {
                free(next);
                return i-j;
            }
        }

        free(next);
        return -1;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item String to Integer (atoi) ，见 \S \ref{sec:string-to-integer}
\myenddot


\section{String to Integer (atoi)} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:string-to-integer}


\subsubsection{描述}
Implement \fn{atoi} to convert a string to an integer.

\textbf{Hint}: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

\textbf{Notes}: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

\textbf{Requirements for atoi}:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, \code{INT_MAX (2147483647)} or \code{INT_MIN (-2147483648)} is returned.

\subsubsection{分析}
细节题。注意几个测试用例：
\begin{enumerate}
\item 不规则输入，但是有效，"-3924x8fc"， "  +  413",
\item 无效格式，" ++c", " ++1"
\item 溢出数据，"2147483648"
\end{enumerate}

\subsubsection{代码}
\begin{Code}
// LeetCode, String to Integer (atoi)
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int myAtoi(const string &str) {
        int num = 0;
        int sign = 1;
        const int n = str.length();
        int i = 0;

        while (str[i] == ' ' && i < n) i++;

        if (str[i] == '+') {
            i++;
        } else if (str[i] == '-') {
            sign = -1;
            i++;
        }

        for (; i < n; i++) {
            if (str[i] < '0' || str[i] > '9')
                break;
            if (num > INT_MAX / 10 ||
                            (num == INT_MAX / 10 &&
                                    (str[i] - '0') > INT_MAX % 10)) {
                return sign == -1 ? INT_MIN : INT_MAX;
            }
            num = num * 10 + str[i] - '0';
        }
        return num * sign;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Implement strStr() ，见 \S \ref{sec:strstr}
\myenddot


\section{Add Binary} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:add-binary}


\subsubsection{描述}
Given two binary strings, return their sum (also a binary string).

For example,
\begin{Code}
a = "11"
b = "1"
\end{Code}
Return {\small \fontspec{Latin Modern Mono} "100"}.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
//LeetCode, Add Binary
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    string addBinary(string a, string b) {
        string result;
        const size_t n = a.size() > b.size() ? a.size() : b.size();
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int carry = 0;
        for (size_t i = 0; i < n; i++) {
            const int ai = i < a.size() ? a[i] - '0' : 0;
            const int bi = i < b.size() ? b[i] - '0' : 0;
            const int val = (ai + bi + carry) % 2;
            carry = (ai + bi + carry) / 2;
            result.insert(result.begin(), val + '0');
        }
        if (carry == 1) {
            result.insert(result.begin(), '1');
        }
        return result;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Add Two Numbers, 见 \S \ref{sec:add-two-numbers}
\myenddot


\section{Longest Palindromic Substring} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:longest-palindromic-substring}


\subsubsection{描述}
Given a string $S$, find the longest palindromic substring in $S$. You may assume that the maximum length of $S$ is 1000, and there exists one unique longest palindromic substring.


\subsubsection{分析}
最长回文子串，非常经典的题。

思路一：暴力枚举，以每个元素为中间元素，同时从左右出发，复杂度$O(n^2)$。

思路二：记忆化搜索，复杂度$O(n^2)$。设\fn{f[i][j]} 表示[i,j]之间的最长回文子串，递推方程如下：
\begin{Code}
f[i][j] = if (i == j) S[i]
          if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
          else max(f[i+1][j-1], f[i][j-1], f[i+1][j])
\end{Code}

思路三：动规，复杂度$O(n^2)$。设状态为\fn{f(i,j)}，表示区间[i,j]是否为回文串，则状态转移方程为
$$
f(i,j)=\begin{cases}
true & ,i=j\\
S[i]=S[j] & , j = i + 1 \\
S[i]=S[j] \text{ and } f(i+1, j-1) & , j > i + 1
\end{cases}
$$

思路四：Manacher’s Algorithm, 复杂度$O(n)$。详细解释见 \myurl{http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html} 。


\subsubsection{备忘录法}
\begin{Code}
// LeetCode, Longest Palindromic Substring
// 备忘录法，会超时
// 时间复杂度O(n^2)，空间复杂度O(n^2)
typedef string::const_iterator Iterator;

namespace std {
template<>
struct hash<pair<Iterator, Iterator>> {
    size_t operator()(pair<Iterator, Iterator> const& p) const {
        return ((size_t) &(*p.first)) ^ ((size_t) &(*p.second));
    }
};
}

class Solution {
public:
    string longestPalindrome(string const& s) {
        cache.clear();
        return cachedLongestPalindrome(s.begin(), s.end());
    }

private:
    unordered_map<pair<Iterator, Iterator>, string> cache;

    string longestPalindrome(Iterator first, Iterator last) {
        size_t length = distance(first, last);

        if (length < 2) return string(first, last);

        auto s = cachedLongestPalindrome(next(first), prev(last));

        if (s.length() == length - 2 && *first == *prev(last))
            return string(first, last);

        auto s1 = cachedLongestPalindrome(next(first), last);
        auto s2 = cachedLongestPalindrome(first, prev(last));

        // return max(s, s1, s2)
        if (s.size() > s1.size()) return s.size() > s2.size() ? s : s2;
        else return s1.size() > s2.size() ? s1 : s2;
    }

    string cachedLongestPalindrome(Iterator first, Iterator last) {
        auto key = make_pair(first, last);
        auto pos = cache.find(key);

        if (pos != cache.end()) return pos->second;
        else return cache[key] = longestPalindrome(first, last);
    }
};
\end{Code}


\subsubsection{动规}
\begin{Code}
// LeetCode, Longest Palindromic Substring
// 动规，时间复杂度O(n^2)，空间复杂度O(n^2)
class Solution {
public:
    string longestPalindrome(const string& s) {
        const int n = s.size();
        bool f[n][n];
        fill_n(&f[0][0], n * n, false);
        // 用 vector 会超时
        //vector<vector<bool> > f(n, vector<bool>(n, false));
        size_t max_len = 1, start = 0;  // 最长回文子串的长度，起点

        for (size_t i = 0; i < s.size(); i++) {
            f[i][i] = true;
            for (size_t j = 0; j < i; j++) {  // [j, i]
                f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1]));
                if (f[j][i] && max_len < (i - j + 1)) {
                    max_len = i - j + 1;
                    start = j;
                }
            }
        }
        return s.substr(start, max_len);
    }
};
\end{Code}


\subsubsection{Manacher’s Algorithm}
\begin{Code}
// LeetCode, Longest Palindromic Substring
// Manacher’s Algorithm
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    // Transform S into T.
    // For example, S = "abba", T = "^#a#b#b#a#$".
    // ^ and $ signs are sentinels appended to each end to avoid bounds checking
    string preProcess(const string& s) {
        int n = s.length();
        if (n == 0) return "^$";

        string ret = "^";
        for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1);

        ret += "#$";
        return ret;
    }

    string longestPalindrome(string s) {
        string T = preProcess(s);
        const int n = T.length();
        // 以T[i]为中心，向左/右扩张的长度，不包含T[i]自己，
        // 因此 P[i]是源字符串中回文串的长度
        int P[n];
        int C = 0, R = 0;

        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i; // equals to i' = C - (i-C)

            P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;

            // Attempt to expand palindrome centered at i
            while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
                P[i]++;

            // If palindrome centered at i expand past R,
            // adjust center based on expanded palindrome.
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }
        }

        // Find the maximum element in P.
        int max_len = 0;
        int center_index = 0;
        for (int i = 1; i < n - 1; i++) {
            if (P[i] > max_len) {
                max_len = P[i];
                center_index = i;
            }
        }

        return s.substr((center_index - 1 - max_len) / 2, max_len);
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Regular Expression Matching} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:regular-expression-matching}


\subsubsection{描述}
Implement regular expression matching with support for \fn{'.'} and \fn{'*'}.

\fn{'.'} Matches any single character.
\fn{'*'} Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
\begin{Code}
bool isMatch(const char *s, const char *p)
\end{Code}

Some examples:
\begin{Code}
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
\end{Code}


\subsubsection{分析}
这是一道很有挑战的题。


\subsubsection{递归版}
\begin{Code}
// LeetCode, Regular Expression Matching
// 递归版，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    bool isMatch(const string& s, const string& p) {
        return isMatch(s.c_str(), p.c_str());
    }
private:
    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') return *s == '\0';

        // next char is not '*', then must match current character
        if (*(p + 1) != '*') {
            if (*p == *s || (*p == '.' && *s != '\0'))
                return isMatch(s + 1, p + 1);
            else
                return false;
        } else { // next char is '*'
            while (*p == *s || (*p == '.' && *s != '\0')) {
                if (isMatch(s, p + 2))
                    return true;
                s++;
            }
            return isMatch(s, p + 2);
        }
    }
};
\end{Code}


\subsubsection{迭代版}
\begin{Code}

\end{Code}


\subsubsection{相关题目}
\begindot
\item Wildcard Matching, 见 \S \ref{sec:wildcard-matching}
\myenddot


\section{Wildcard Matching} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:wildcard-matching}


\subsubsection{描述}
Implement wildcard pattern matching with support for \fn{'?'} and \fn{'*'}.

\fn{'?'} Matches any single character.
\fn{'*'} Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
\begin{Code}
bool isMatch(const char *s, const char *p)
\end{Code}

Some examples:
\begin{Code}
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
\end{Code}


\subsubsection{分析}
跟上一题很类似。

主要是\fn{'*'}的匹配问题。\fn{p}每遇到一个\fn{'*'}，就保留住当前\fn{'*'}的坐标和\fn{s}的坐标，然后\fn{s}从前往后扫描，如果不成功，则\fn{s++}，重新扫描。


\subsubsection{递归版}
\begin{Code}
// LeetCode, Wildcard Matching
// 递归版，会超时，用于帮助理解题意
// 时间复杂度O(n!*m!)，空间复杂度O(n)
class Solution {
public:
    bool isMatch(const string& s, const string& p) {
        return isMatch(s.c_str(), p.c_str());
    }
private:
    bool isMatch(const char *s, const char *p) {
        if (*p == '*') {
            while (*p == '*') ++p;  //skip continuous '*'
            if (*p == '\0') return true;
            while (*s != '\0' && !isMatch(s, p)) ++s;

            return *s != '\0';
        }
        else if (*p == '\0' || *s == '\0') return *p == *s;
        else if (*p == *s || *p == '?') return isMatch(++s, ++p);
        else return false;
    }
};
\end{Code}


\subsubsection{迭代版}
\begin{Code}
// LeetCode, Wildcard Matching
// 迭代版，时间复杂度O(n*m)，空间复杂度O(1)
class Solution {
public:
    bool isMatch(const string& s, const string& p) {
        return isMatch(s.c_str(), p.c_str());
    }
private:
    bool isMatch(const char *s, const char *p) {
        bool star = false;
        const char *str, *ptr;
        for (str = s, ptr = p; *str != '\0'; str++, ptr++) {
            switch (*ptr) {
            case '?':
                break;
            case '*':
                star = true;
                s = str, p = ptr;
                while (*p == '*') p++;  //skip continuous '*'
                if (*p == '\0') return true;
                str = s - 1;
                ptr = p - 1;
                break;
            default:
                if (*str != *ptr) {
                    // 如果前面没有'*'，则匹配不成功
                    if (!star) return false;
                    s++;
                    str = s - 1;
                    ptr = p - 1;
                }
            }
        }
        while (*ptr == '*') ptr++;
        return (*ptr == '\0');
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Regular Expression Matching, 见 \S \ref{sec:regular-expression-matching}
\myenddot


\section{Longest Common Prefix} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:longest-common-prefix}


\subsubsection{描述}
Write a function to find the longest common prefix string amongst an array of strings.


\subsubsection{分析}
从位置0开始，对每一个位置比较所有字符串，直到遇到一个不匹配。


\subsubsection{纵向扫描}
\begin{Code}
// LeetCode, Longest Common Prefix
// 纵向扫描，从位置0开始，对每一个位置比较所有字符串，直到遇到一个不匹配
// 时间复杂度O(n1+n2+...)
// @author 周倩 (http://weibo.com/zhouditty)
class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.empty()) return "";

        for (int idx = 0; idx < strs[0].size(); ++idx) { // 纵向扫描
            for (int i = 1; i < strs.size(); ++i) {
                if (strs[i][idx] != strs[0][idx]) return strs[0].substr(0,idx);
            }
        }
        return strs[0];
    }
};
\end{Code}


\subsubsection{横向扫描}
\begin{Code}
// LeetCode, Longest Common Prefix
// 横向扫描，每个字符串与第0个字符串，从左到右比较，直到遇到一个不匹配，
// 然后继续下一个字符串
// 时间复杂度O(n1+n2+...)
class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.empty()) return "";

        int right_most = strs[0].size() - 1;
        for (size_t i = 1; i < strs.size(); i++)
            for (int j = 0; j <= right_most; j++)
                if (strs[i][j] != strs[0][j])  // 不会越界，请参考string::[]的文档
                    right_most = j - 1;

        return strs[0].substr(0, right_most + 1);
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Valid Number} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:valid-number}


\subsubsection{描述}
Validate if a given string is numeric.

Some examples:
\begin{Code}
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
\end{Code}

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.


\subsubsection{分析}
细节实现题。

本题的功能与标准库中的\fn{strtod()}功能类似。


\subsubsection{有限自动机}
\begin{Code}
// LeetCode, Valid Number
// @author 龚陆安 (http://weibo.com/luangong)
// finite automata，时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    bool isNumber(const string& s) {
        enum InputType {
            INVALID,    // 0
            SPACE,      // 1
            SIGN,       // 2
            DIGIT,      // 3
            DOT,        // 4
            EXPONENT,   // 5
            NUM_INPUTS  // 6
        };
        const int transitionTable[][NUM_INPUTS] = {
                -1, 0, 3, 1, 2, -1, // next states for state 0
                -1, 8, -1, 1, 4, 5,     // next states for state 1
                -1, -1, -1, 4, -1, -1,     // next states for state 2
                -1, -1, -1, 1, 2, -1,     // next states for state 3
                -1, 8, -1, 4, -1, 5,     // next states for state 4
                -1, -1, 6, 7, -1, -1,     // next states for state 5
                -1, -1, -1, 7, -1, -1,     // next states for state 6
                -1, 8, -1, 7, -1, -1,     // next states for state 7
                -1, 8, -1, -1, -1, -1,     // next states for state 8
                };

        int state = 0;
        for (auto ch : s) {
            InputType inputType = INVALID;
            if (isspace(ch))
                inputType = SPACE;
            else if (ch == '+' || ch == '-')
                inputType = SIGN;
            else if (isdigit(ch))
                inputType = DIGIT;
            else if (ch == '.')
                inputType = DOT;
            else if (ch == 'e' || ch == 'E')
                inputType = EXPONENT;

            // Get next state from current state and input symbol
            state = transitionTable[state][inputType];

            // Invalid input
            if (state == -1) return false;
        }
        // If the current state belongs to one of the accepting (final) states,
        // then the number is valid
        return state == 1 || state == 4 || state == 7 || state == 8;

    }
};
\end{Code}


\subsubsection{使用strtod()}
\begin{Code}
// LeetCode, Valid Number
// @author 连城 (http://weibo.com/lianchengzju)
// 偷懒，直接用 strtod()，时间复杂度O(n)
class Solution {
public:
    bool isNumber (const string& s) {
        return isNumber(s.c_str());
    }
private:
    bool isNumber (char const* s) {
        char* endptr;
        strtod (s, &endptr);

        if (endptr == s) return false;

        for (; *endptr; ++endptr)
            if (!isspace (*endptr)) return false;

        return true;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Integer to Roman} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:integer-to-roman}


\subsubsection{描述}
Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.


\subsubsection{分析}
无


\subsubsection{代码}
\begin{Code}
// LeetCode, Integer to Roman
// 时间复杂度O(num)，空间复杂度O(1)
class Solution {
public:
    string intToRoman(int num) {
        const int radix[] = {1000, 900, 500, 400, 100, 90,
                50, 40, 10, 9, 5, 4, 1};
        const string symbol[] = {"M", "CM", "D", "CD", "C", "XC",
                "L", "XL", "X", "IX", "V", "IV", "I"};

        string roman;
        for (size_t i = 0; num > 0; ++i) {
            int count = num / radix[i];
            num %= radix[i];
            for (; count > 0; --count) roman += symbol[i];
        }
        return roman;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Roman to Integer, 见 \S \ref{sec:roman-to-integer}
\myenddot


\section{Roman to Integer} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:roman-to-integer}


\subsubsection{描述}
Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.


\subsubsection{分析}
从前往后扫描，用一个临时变量记录分段数字。

如果当前比前一个大，说明这一段的值应该是当前这个值减去上一个值。比如\fn{IV = 5 – 1}；否则，将当前值加入到结果中，然后开始下一段记录。比如\fn{VI = 5 + 1, II=1+1}


\subsubsection{代码}
\begin{Code}
// LeetCode, Roman to Integer
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    inline int map(const char c) {
        switch (c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
        }
    }

    int romanToInt(const string& s) {
        int result = 0;
        for (size_t i = 0; i < s.size(); i++) {
            if (i > 0 && map(s[i]) > map(s[i - 1])) {
                result += (map(s[i]) - 2 * map(s[i - 1]));
            } else {
                result += map(s[i]);
            }
        }
        return result;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item Integer to Roman, 见 \S \ref{sec:integer-to-roman}
\myenddot


\section{Count and Say} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:count-and-say}


\subsubsection{描述}
The count-and-say sequence is the sequence of integers beginning as follows:
\begin{Code}
1, 11, 21, 1211, 111221, ...
\end{Code}

\fn{1} is read off as \fn{"one 1"} or \fn{11}.

\fn{11} is read off as \fn{"two 1s"} or \fn{21}.

\fn{21} is read off as \fn{"one 2"}, then \fn{"one 1"} or \fn{1211}.

Given an integer $n$, generate the nth sequence.

Note: The sequence of integers will be represented as a string.


\subsubsection{分析}
模拟。


\subsubsection{代码}
\begin{Code}
// LeetCode, Count and Say
// @author 连城 (http://weibo.com/lianchengzju)
// 时间复杂度O(n^2)，空间复杂度O(n)
class Solution {
public:
    string countAndSay(int n) {
        string s("1");

        while (--n)
            s = getNext(s);

        return s;
    }

    string getNext(const string &s) {
        stringstream ss;

        for (auto i = s.begin(); i != s.end(); ) {
            auto j = find_if(i, s.end(), bind1st(not_equal_to<char>(), *i));
            ss << distance(i, j) << *i;
            i = j;
        }

        return ss.str();
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Anagrams} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:anagrams}


\subsubsection{描述}
Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.


\subsubsection{分析}
Anagram（回文构词法）是指打乱字母顺序从而得到新的单词，比如 \fn{"dormitory"} 打乱字母顺序会变成 \fn{"dirty room"} ，\fn{"tea"} 会变成\fn{"eat"}。

回文构词法有一个特点：单词里的字母的种类和数目没有改变，只是改变了字母的排列顺序。因此，将几个单词按照字母顺序排序后，若它们相等，则它们属于同一组 anagrams 。


\subsubsection{代码}
\begin{Code}
// LeetCode, Anagrams
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        unordered_map<string, vector<string> > group;
        for (const auto &s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            group[key].push_back(s);
        }

        vector<string> result;
        for (auto it = group.cbegin(); it != group.cend(); it++) {
            if (it->second.size() > 1)
                result.insert(result.end(), it->second.begin(), it->second.end());
        }
        return result;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Simplify Path} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:simplify-path}


\subsubsection{描述}
Given an absolute path for a file (Unix-style), simplify it.

For example, \\
path = \fn{"/home/"}, => \fn{"/home"} \\
path = \fn{"/a/./b/../../c/"}, => \fn{"/c"} \\

Corner Cases:
\begindot
\item Did you consider the case where path = \fn{"/../"}? 
In this case, you should return \fn{"/"}.
\item 
Another corner case is the path might contain multiple slashes \fn{'/'} together, such as \fn{"/home//foo/"}.
In this case, you should ignore redundant slashes and return \fn{"/home/foo"}.
\myenddot


\subsubsection{分析}
很有实际价值的题目。


\subsubsection{代码}
\begin{Code}
// LeetCode, Simplify Path
// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
    string simplifyPath(const string& path) {
        vector<string> dirs; // 当做栈

        for (auto i = path.begin(); i != path.end();) {
            ++i;

            auto j = find(i, path.end(), '/');
            auto dir = string(i, j);

            if (!dir.empty() && dir != ".") {// 当有连续 '///'时，dir 为空
                if (dir == "..") {
                    if (!dirs.empty())
                        dirs.pop_back();
                } else
                    dirs.push_back(dir);
            }

            i = j;
        }

        stringstream out;
        if (dirs.empty()) {
            out << "/";
        } else {
            for (auto dir : dirs)
                out << '/' << dir;
        }

        return out.str();
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot


\section{Length of Last Word} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:length-of-last-word}


\subsubsection{描述}
Given a string s consists of upper/lower-case alphabets and empty space characters \fn{' '}, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given \fn{s = "Hello World"},
return 5.


\subsubsection{分析}
细节实现题。


\subsubsection{用 STL}
\begin{Code}
// LeetCode, Length of Last Word
// 偷懒，用 STL
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int lengthOfLastWord(const string& s) {
        auto first = find_if(s.rbegin(), s.rend(), ::isalpha);
        auto last = find_if_not(first, s.rend(), ::isalpha);
        return distance(first, last);
    }
};
\end{Code}


\subsubsection{顺序扫描}
\begin{Code}
// LeetCode, Length of Last Word
// 顺序扫描，记录每个 word 的长度
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
    int lengthOfLastWord(const string& s) {
        return lengthOfLastWord(s.c_str());
    }
private:
    int lengthOfLastWord(const char *s) {
        int len = 0;
        while (*s) {
            if (*s++ != ' ')
                ++len;
            else if (*s && *s != ' ')
                len = 0;
        }
        return len;
    }
};
\end{Code}


\subsubsection{相关题目}
\begindot
\item 无
\myenddot