Photo by davide ragusa on Unsplash

11. String

-

11. 1. Palindrome

A palindrome is a word or phrase that is spelled the exact same when reading it forwards or backward. Palindromes are allowed to be lowercase or uppercase, contain spaces, punctuation, and word dividers.

Algorithms that check for palindromes are a common programming interview question.

The word racecar is a valid palindrome, as it is a word spelled the same when backgrounds and forwards. The examples below shows valid cases of the palindrome racecar.

|     |
racecar -> r == r

 |   |
racecar -> a == a

  | |
racecar -> c == c

   |
racecar -> left index == right index -> return true

To check for palindromes, a string’s characters are compared starting from the beginning and end then moving inward toward the middle of the string while maintaining the same distance apart. In this implementation of a palindrome algorithm, recursion is used to check each of the characters on the left-hand side and right-hand side moving inward.

func isPalindrome(_ str: String) -> Bool {
    let strippedString = str.replacingOccurrences(of: "\\W", with: "", options: .regularExpression, range: nil)
    let length = strippedString.count
    
    if length > 1 {
        return palindrome(strippedString.lowercased(), left: 0, right: length - 1)
    }
    
    return false
}
private func palindrome(_ str: String, left: Int, right: Int) -> Bool {
    if left >= right {
        return true
    }
    
    let lhs = str[str.index(str.startIndex, offsetBy: left)]
    let rhs = str[str.index(str.startIndex, offsetBy: right)]
    
    if lhs != rhs {0
        return false
    }
    
    return palindrome(str, left: left + 1, right: right - 1)
}

11. 2. Manacher’s Algorithm

Manacher’s algorithm is an algorithm for finding a palindrome in a string, and the time complexity is O (n) (where n is the length of the string)

The algorithm takes the string S as input and returns:

• An integer array A having the same length as the string S, and the element A [i] of each A is the length of the longest radial radius of the i-th string (ie, S[(i−A[i])⋯(i+A[i])] is a sold string and S[(i−A[i]−1)⋯(i+A[i]+1)] is not a sold string )

For example, for the input S = ‘banana’, the result of A is:

The algorithm is as follows:

1. i proceeds from 0 to n-1 (n = | S |)
2. R = max (j + A [j]) for all j with j < i, Let j be p. (R = p + A [p])
3. the initial value of A [i] is determined depending on whether or not i ≤ R

• If i> R, the initial value of A [i] is zero.
• If i ≤ R, then i is a soldin dump centered on p. At this time, we obtain the symmetric point i ‘of i around p. The initial value of A [i] is min (R-i, A [i ‘])

4. From the initial value of A [i], A [i] is incremented until S [i-A [i]] and S [i + A [i]] are equal, and then to i.

Pseudo Code of Manacher’s Algorithm

11. 3. Trie

Means an ordered set of tree data structures used to store dynamic sets or associative arrays with strings. Unlike a binary search tree, nodes on a tree do not store keys associated with that node. Instead, the position on the tree represents the current key. Every descendant of a particular node has the same prefix as the node, and the root node has an empty string. The value does not exist in all nodes, but exists only at the leaf nodes or the inner node corresponding to the specific key. To optimize the space usage of the prefix tree, a compact prefix tree was envisioned. The word trie comes from the word reTRIEval. Edward Fredkin, who created this word, pronounces the word the same as ‘tree’, but others pronounce it as ‘trai’.

Why should I use TRIE?
To quickly and efficiently search large amounts of text information
So Trie is a data structure that can effectively retrieve dictionary or Internet autocompletion.

As mentioned earlier, the name TRIE came from TREE RETRIEVAL. The most typical characteristic is that the keyword information has only the last node, the remaining nodes have no information and only the link.

11. 4. Suffix Tree

Suffix tree is a trie shaped data structure that represents all suffixes of a string.
The trie is called a prefix tree. The difference between the data structures is that when there is a word banana, the trie stores only the word banana, but the suffix tree is like banana, anana, nana, ana, na, a It saves the number of all cases that can come from the word banana. The reason for storing all of the cases in vain is because you need to search for strings. In the case of the Trie data structure, you can find the complete word banana as a partial word such as ban, ba, but you can not find banana with the words nan, ana. To solve this problem, it seems to be a suffix tree that improved the trie.

Since the edge can have a string label, a distinction must be made between the two meanings of ‘depth’. The first is node depth. The node depth refers to how many edges must pass from the root to the node. The second is Label depth. This is the total length of the edge label for the edge in the path from root to node.