Skip to content

3327. Check if DFS Strings Are Palindromes 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
 public:
  vector<bool> findAnswer(vector<int>& parent, string s) {
    const int n = parent.size();
    vector<bool> ans(n);
    vector<vector<int>> tree(n);
    vector<int> start(n);  // start[i] := the start index of `dfsStr` of node i
    vector<int> end(n);    // end[i] := the end index of `dfsStr` of node i
    string dfsStr;

    for (int i = 1; i < n; ++i)
      tree[parent[i]].push_back(i);

    dfs(tree, 0, /*index=*/0, s, start, end, dfsStr);
    const string t = join('@' + dfsStr + '$', /*delimiter=*/'#');
    const vector<int> p = manacher(t);

    for (int i = 0; i < n; ++i)
      ans[i] = isPalindrome(start[i], end[i], p);

    return ans;
  }

 private:
  // Returns the start index of the "DFS string" of u's next node.
  int dfs(const vector<vector<int>>& tree, int u, int index, const string& s,
          vector<int>& start, vector<int>& end, string& dfsStr) {
    start[u] = index;
    for (const int v : tree[u])
      index = dfs(tree, v, index, s, start, end, dfsStr);
    end[u] = index;
    dfsStr += s[u];
    return index + 1;
  }

  // Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
  // centered at `t[i]`, where `t` is a string with delimiters and sentinels.
  vector<int> manacher(const string& t) {
    vector<int> p(t.length());
    int center = 0;
    for (int i = 1; i < t.length() - 1; ++i) {
      const int rightBoundary = center + p[center];
      const int mirrorIndex = center - (i - center);
      if (rightBoundary > i)
        p[i] = min(rightBoundary - i, p[mirrorIndex]);
      // Try to expand the palindrome centered at i.
      while (t[i + 1 + p[i]] == t[i - 1 - p[i]])
        ++p[i];
      // If a palindrome centered at i expands past `rightBoundary`, adjust
      // the center based on the expanded palindrome.
      if (i + p[i] > rightBoundary)
        center = i;
    }
    return p;
  }

  // Returns true if `dfsStr[s..e]` is a palindrome by using the precomputed
  // array `p` from the Manacher's algorithm.
  //
  // The precomputed array `p` is based on the string `t` with delimiters and
  // sentinels. Let `t = '#'.join('@' + dfsStr + '$')`. Then, the center of
  // `dfsStr` maps to `t[s + e + 2]` since `dfsStr[s]` maps to `t[2 * s + 2]`
  // and `dfsStr[e]` maps to `t[2 * e + 2]`. So, the center of `dfsStr` is
  // `t[(2 * s + 2 + 2 * e + 2) / 2] = t[s + e + 2]`.
  bool isPalindrome(int s, int e, const vector<int>& p) {
    const int length = e - s + 1;
    const int center = s + e + 2;
    return p[center] >= length;
  }

  string join(const string& s, char delimiter) {
    string joined;
    for (int i = 0; i < s.length() - 1; ++i) {
      joined += s[i];
      joined += delimiter;
    }
    joined += s.back();
    return joined;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
  public boolean[] findAnswer(int[] parent, String s) {
    final int n = parent.length;
    boolean[] ans = new boolean[n];
    List<Integer>[] tree = new List[n];
    // start[i] := the start index of `dfsStr` of node i
    int[] start = new int[n];
    // end[i] := the end index of `dfsStr` of node i
    int[] end = new int[n];

    for (int i = 0; i < n; ++i)
      tree[i] = new ArrayList<>();

    StringBuilder dfsStr = new StringBuilder();

    for (int i = 1; i < n; ++i)
      tree[parent[i]].add(i);

    dfs(tree, 0, /*index=*/0, s, start, end, dfsStr);
    final String t = join('@' + dfsStr.toString() + '$', '#');
    final int[] p = manacher(t);

    for (int i = 0; i < n; ++i)
      ans[i] = isPalindrome(start[i], end[i], p);

    return ans;
  }

  // Returns the start index of the "DFS string" of u's next node.
  private int dfs(List<Integer>[] tree, int u, int index, final String s, int[] start, int[] end,
                  StringBuilder dfsStr) {
    start[u] = index;
    for (final int v : tree.get(u))
      index = dfs(tree, v, index, s, start, end, dfsStr);
    end[u] = index;
    dfsStr.append(s.charAt(u));
    return index + 1;
  }

  // Returns true if `dfsStr[s..e]` is a palindrome by using the precomputed
  // array `p` from the Manacher's algorithm.
  //
  // The precomputed array `p` is based on the string `t` with delimiters and
  // sentinels. Let `t = '#'.join('@' + dfsStr + '$')`. Then, the center of
  // `dfsStr` maps to `t[s + e + 2]` since `dfsStr[s]` maps to `t[2 * s + 2]`
  // and `dfsStr[e]` maps to `t[2 * e + 2]`. So, the center of `dfsStr` is
  // `t[(2 * s + 2 + 2 * e + 2) / 2] = t[s + e + 2]`.
  private boolean isPalindrome(int s, int e, int[] p) {
    final int length = e - s + 1;
    final int center = s + e + 2;
    return p[center] >= length;
  }

  // Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
  // centered at `t[i]`, where `t` is a string with delimiters and sentinels.
  private int[] manacher(final String t) {
    int[] p = new int[t.length()];
    int center = 0;
    for (int i = 1; i < t.length() - 1; ++i) {
      int rightBoundary = center + p[center];
      int mirrorIndex = center - (i - center);
      if (rightBoundary > i)
        p[i] = Math.min(rightBoundary - i, p[mirrorIndex]);
      // Try to expand the palindrome centered at i.
      while (i + 1 + p[i] < t.length() && i - 1 - p[i] >= 0 &&
             t.charAt(i + 1 + p[i]) == t.charAt(i - 1 - p[i]))
        ++p[i];
      // If a palindrome centered at i expands past `rightBoundary`, adjust
      // the center based on the expanded palindrome.
      if (i + p[i] > rightBoundary) {
        center = i;
      }
    }
    return p;
  }

  private String join(final String s, char delimiter) {
    StringBuilder joined = new StringBuilder();
    for (int i = 0; i < s.length() - 1; ++i) {
      joined.append(s.charAt(i));
      joined.append(delimiter);
    }
    joined.append(s.charAt(s.length() - 1));
    return joined.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution:
  def findAnswer(self, parent: list[int], s: str) -> list[bool]:
    n = len(parent)
    tree = [[] for _ in parent]
    start = [0] * n  # start[i] := the start index of `dfsStr` of node i
    end = [0] * n  # end[i] := the end index of `dfsStr` of node i
    dfsStr = []

    for i in range(1, n):
      tree[parent[i]].append(i)

    self._dfs(tree, 0, 0, s, start, end, dfsStr)
    t = '#'.join('@' + ''.join(dfsStr) + '$')
    p = self._manacher(t)
    return [self._isPalindrome(s, e, p)
            for s, e in zip(start, end)]

  def _dfs(
      self,
      tree: list[list[int]],
      u: int,
      index: int,
      s: str,
      start: list[int],
      end: list[int],
      dfsStr: list[str]
  ) -> int:
    """Returns the start index of the "DFS string" of u's next node."""
    start[u] = index
    for v in tree[u]:
      index = self._dfs(tree, v, index, s, start, end, dfsStr)
    end[u] = index
    dfsStr.append(s[u])
    return index + 1

  def _manacher(self, t: str) -> list[int]:
    """
    Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
    centered at `t[i]`, where `t` is a string with delimiters and sentinels.
    """
    p = [0] * len(t)
    center = 0
    for i in range(1, len(t) - 1):
      rightBoundary = center + p[center]
      mirrorIndex = center - (i - center)
      if rightBoundary > i:
        p[i] = min(rightBoundary - i, p[mirrorIndex])
      # Try to expand the palindrome centered at i.
      while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
        p[i] += 1
      # If a palindrome centered at i expands past `rightBoundary`, adjust
      # the center based on the expanded palindrome.
      if i + p[i] > rightBoundary:
        center = i
    return p

  def _isPalindrome(self, s: int, e: int, p: list[int]) -> bool:
    """
    Returns true if `dfsStr[s..e]` is a palindrome by using the precomputed
    array `p` from the Manacher's algorithm.

    The precomputed array `p` is based on the string `t` with delimiters and
    sentinels. Let `t = '#'.join('@' + dfsStr + '$')`. Then, the center of
    `dfsStr` maps to `t[s + e + 2]` since `dfsStr[s]` maps to `t[2 * s + 2]`
    and `dfsStr[e]` maps to `t[2 * e + 2]`. So, the center of `dfsStr` is
    `t[(2 * s + 2 + 2 * e + 2) / 2] = t[s + e + 2]`.
    """
    length = e - s + 1
    center = s + e + 2
    return p[center] >= length