2.2.1. Questions

2.2.1.1. Decode String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

input: "3[a]2[bc]", output: "aaabcbc".
input: "3[a2[c]]", output: "accaccacc".
input: "2[abc]3[cd]ef", output: "abcabccdcdcdef".

leetcode

The original problem and its subproblem have the same structure, so this problem can be easily done with a recursive function or DFS. It is very important to clearly define the input and output of the recursive function. In this case, the output is the resulting string from square bracket pair […], and the input is the original string and index. We can write code like:

 1struct Solution {
 2    string decodeString(string s) {
 3        int i = 0;
 4        return rec(s, i);
 5    }
 6    string rec(string& s, int& i) {
 7        string r; // final result
 8        int m = 0; // multiplier
 9        for (; i<s.size(); i++) {
10            if (isalpha(s[i]))
11                r += s[i];
12            else if (isdigit(s[i]))
13                m = m * 10 + s[i] - '0';
14            else if (s[i] == '[') {
15                i++;////
16                string t = rec(s, i);
17                while (m) r += t, m--;
18            } else if (s[i] == ']')
19                return r;////
20        }
21        return r;
22    }
23};

The input also has a parenthesis structure(ref to:CLRS page 606). DFS is actually a recursive algorithm.

2.2.1.2. Shortest Length of Folding String

Given a string and folding rule, find the length of its shortest fold.

The folding rule is:

1. A string can be regarded as its own fold. Denoted as S ~ S
2. X(S) is a fold of a string of X(X>1) Ss connected together. Denoted as X(S) ~ SSSS...S(X S).
3. If A ~ A', B ~ B', then AB ~ A'B'.
   For example, because 3(A) = AAA, 2(B) = BB, so 3(A)C2(B) ~ AAACBB, and 2(3(A)C)2(B) ~ AAACAAACBB

For example, the shortest fold of AAAAAAAAAABABABCCCD is: 9(A)3(AB)CCD.

Example:

input: "NEERCYESYESYESNEERCYESYESYES", output: 14.
Explanation: A shortest fold is: 2(NEERC3(YES)) and length of string 2(NEERC3(YES)) is 14.

dp[l][r] to denote the shortest fold length of s[l:r]

There is formula:

dp[l][r] = min(r-l+1, dp[l][k] + dp[k+1][r]) where l<=k<r

But there is a edge case will make this formula fail. If s is a string with 10 repeated abc, then abc9(abc) and 9(abc)abc will be the solution, which is wrong. To fix this, we need to consider the case when [k+1][r] can be derived from repeating [l][k]:

dp[l][r]=min(dp[l][r],dp[l][k]+2+IntLen((r-l+1)/(k-l+1)))；

 1struct Solution {
 2  string s;
 3  vector<vector<int>> results;
 4  bool is_multipler_string(int l, int r, int cl, int cr) {
 5    if ((r - l + 1) % (cr - cl + 1) != 0)
 6      return 0;
 7    for (int i = l; i <= r; i++)
 8      if (s[i] != s[(i - l) % (cr - cl + 1) + cl])
 9        return 0;
10    return 1;
11  }
12  int int_length(int x) {
13    int t = 0;
14    while (x) {
15      x /= 10;
16      t++;
17    }
18    return t;
19  }
20  int dp(int l, int r) {
21    if (l == r)
22      return 1;
23    if (results[l][r])
24      return results[l][r];
25    int t = r - l + 1;
26    for (int i = l; i < r; i++) {
27      t = min(t, dp(l, i) + dp(i + 1, r));
28      if (is_multipler_string(i + 1, r, l, i))
29        t = min(t, dp(l, i) + 2 + int_length((r - l + 1) / (i - l + 1)));
30    }

TC:O(N^2), SC:O(N^2)

This is a top-down DP.

http://hzwer.com/1905.html Refer to: BZOJ1090, SCOI2003

2.2.1.3. Repeated Substring Pattern

Given a string str, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Examples:

Input: str = "abcabcabc"
Output: true
The given string is 3 times repetition of "abc"

Input: str = "abadabad"
Output: true
The given string is 2 times repetition of "abad"

Input: str = "aabaabaabaab"
Output: true
The given string is 4 times repetition of "aab"

Input: str = "abcdabc"
Output: false

  • Brute Force

     1namespace repeated {
 2class Solution {
 3  bool f(string s, int l) { // TC: O(N), SC: O(1)
 4    if (s.size() % l != 0 or s.size() <= l) {
 5      return false;
 6    }
 7    for (int j = l; j < s.size(); j++) {
 8      if (s[(j - l) % l] != s[j]) {
 9        return false;
10      }
11    }
12    return true;
13  }
14
15public:
16  bool repeatedSubstringPattern(string s) { // TC: O(N^2), SC: O(1)
17    if (s.size() <= 1)
18      return false;
19    for (int i = 0; i < s.size() / 2 + 1; i++) {
20      if (f(s, i + 1))
21        return true;
22    }
23    return false;

  • LPPP (longest proper prefix and postfix)

2.2.1.4. Longest Palindromic Prefix

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Input: s = "aacecaaa", Output: "aaacecaaa"
Input: s = "abcd", Output: "dcbabcd"

  • Brute Force (T:O(N^2), SC:O(1))

     1bool is_pal(string s, int h, int t) {
 2  while (h < t)
 3    if (s[h++] != s[t--])
 4      return false;
 5  return true;
 6}
 7string longest_palindromic_prefix_v1(string s) {
 8  if (s.empty())
 9    return s;
10  int l = 0;
11  for (int i = 0; i < s.size(); i++)
12    if (is_pal(s, 0, i))
13      l = i;
14  auto t = s.substr(l + 1);
15  reverse(t.begin(), t.end());
16  return t + s;
17}
18
19string longest_palindromic_prefix_v2(string s) {

  • Rolling Hash (T:O(N), SC:O(1))

 1string longest_palindromic_prefix_v2(string s) {
 2  if (s.size() <= 1)
 3    return s;
 4  int r = 0, hash1 = 0, hash2 = 0, BASE = 37, POW = 1;
 5  for (int i = 0; i < s.size(); ++i) {
 6    hash1 = hash1 * BASE + s[i];
 7    hash2 = hash2 + s[i] * POW;
 8    if (hash1 == hash2)
 9      r = i;
10    POW *= BASE;
11  }
12  string tmp = s.substr(r + 1); // :-)
13  reverse(tmp.begin(), tmp.end());
14  return tmp + s;
15}

💡

2.2.1.5. Guess Word

给一个target单词，一个guess单词，如果位置完全匹配是G，字母匹配但是位置不匹配是Y，否则是R。如果有多个可以匹配为Y的，则把index最小的匹配成Y，其他的还是R，然后输出结果的string。 比如BACD和CAGE，就输出YGRR。

follow up是如果给一个target和a sequence of guess words，每一步要求前一步的guess是G的地方需要retain，前一步如果是Y的corresponding letter must be included in这个单词。输出这sequence of guess words是不是全部valid.

比如说我的target是ABCDE, 我有一个guess word的序列，The first guess word是AGHBD，那么第一步得到的结果就是GRRYY， 下一步的话valid的guess就可以是比如ACBDG（G的位置必须index和值都还是原来的，所以第一个位置必须是A，Y的地方必需至少包含，所以必须包含BD），像AGHYU或者BDAHG就不行 给一个guess word的list，判断是不是每次猜测都是基于前一步的guess的valid guess

Example:
target: ABCDE, guess words: {"AGHBD","ACBDG","AFBDC","ABCDE"}, output: true
target: ABCDE, guess words: {"AGHBD","AGHYU"}, output: false
target: ABCDE, guess words: {"AGHBD","BDAHG"}, output: false

 1#include <gtest/gtest.h>
 2#include <sein.hpp>
 3
 4namespace ns_string_guess {
 5
 6string guess_result(string secret, string guess) {
 7  if (secret.size() != guess.size()) throw invalid_argument("length mismatches");
 8  vector<int> counter(128, -1); // ascii table length is 128
 9  for (int i = secret.size() - 1; i >= 0; i--)
10    counter[secret[i]] = i;
11  string res(secret.size(), 'G');
12  for (int i = 0; i < secret.size(); i++) {
13    if (secret[i] == guess[i]) {
14      continue;
15    } else if (counter.at(guess[i]) > 0) {
16      res[i] = 'Y', counter[guess[i]] = -1; // 💣
17    } else res[i] = 'R';
18  }
19  return res;
20}
21
22// TC: O(MN)
23bool valid_guess_sequence(string secret, vector<string> guess_words) {
24  unordered_set<int> match_indices;
25  unordered_set<char> contains;
26  vector<int> counter(128, -1); // ascii table length is 128
27  for (int i = secret.size() - 1; i >= 0; i--)
28    counter[secret[i]] = i;
29  for (const string &g: guess_words) {
30    if (secret.size() != g.size()) return false;
31    auto _contains = contains;
32    auto _counter = counter;
33    for (int i = 0; i < secret.size(); i++) {
34      if (match_indices.count(i) and secret[i] != g[i]) return false;
35      if (secret[i] == g[i]) match_indices.insert(i);
36      if (_contains.count(g[i])) {
37        _contains.erase(g[i]);
38        continue;
39      }
40      if (_counter[g[i]] > 0) { // new char
41        contains.insert(g[i]), _counter[g[i]] = -1;
42      } // 💣
43    }
44    if (!_contains.empty()) return false;
45  }
46  return true;
47}
48
49}
50using namespace ns_string_guess;
51TEST(_string_guess, a) {
52  EXPECT_EQ(guess_result("BACDF", "CAGEC"), "YGRRR");
53  EXPECT_TRUE(valid_guess_sequence("ABCDE", {"AGHBD", "ACBDG", "AFBDC", "ABCDE"}));
54  EXPECT_FALSE(valid_guess_sequence("ABCDE", {"AGHBD", "ACBDG", "AFBDE"}));
55  EXPECT_FALSE(valid_guess_sequence("ABCDE", {"AGHBD", "ACBDG", "ABBDE"}));
56}