Recursive Algorithm to Encrypte a String

  • 时间:2020-10-07 14:14:07
  • 分类:网络文摘
  • 阅读:97 次

You’ve devised a simple encryption method for alphabetic strings that shuffles the characters in such a way that the resulting string is hard to quickly read, but is easy to convert back into the original string.

When you encrypt a string S, you start with an initially-empty resulting string R and append characters to it as follows:
Append the middle character of S (if S has even length, then we define the middle character as the left-most of the two central characters)
Append the encrypted version of the substring of S that’s to the left of the middle character (if non-empty)
Append the encrypted version of the substring of S that’s to the right of the middle character (if non-empty)

For example, to encrypt the string “abc”, we first take “b”, and then append the encrypted version of “a” (which is just “a”) and the encrypted version of “c” (which is just “c”) to get “bac”.

If we encrypt “abcxcba” we’ll get “xbacbca”. That is, we take “x” and then append the encrypted version “abc” and then append the encrypted version of “cba”.

Input
S contains only lower-case alphabetic characters
1 <= |S| <= 10,000
Output
Return string R, the encrypted version of S.

Example 1
S = “abc”
R = “bac”

Example 2
S = “abcd”
R = “bacd”

Example 3
S = “abcxcba”
R = “xbacbca”

Example 4
S = “facebook”
R = “eafcobok”

Encrypted Words by Recursion

The problem is inherently recursive. The algorithm of Encryption can be implemented straightforward by Recursion. First we need to define the terminal cases when the given string is empty or a single character – which we can just return it.

1
2
3
4
5
6
7
string findEncryptedWord(string s) {
  if (s.empty()) return "";
  if (s.size() == 1) return s;
  int mid = (s.size() & 1) ? s.size() / 2 : (s.size() / 2 - 1);
  return s[mid] + findEncryptedWord(s.substr(0, mid)) + 
                  findEncryptedWord(s.substr(mid + 1));
}
string findEncryptedWord(string s) {
  if (s.empty()) return "";
  if (s.size() == 1) return s;
  int mid = (s.size() & 1) ? s.size() / 2 : (s.size() / 2 - 1);
  return s[mid] + findEncryptedWord(s.substr(0, mid)) + 
                  findEncryptedWord(s.substr(mid + 1));
}

Then, we can divide the string by middle into half – recursively obtaining the encrypted strings of both parts, then concatenate the three parts recursively. The time complexity is O(N) if we consider the string concatenation time is O(1) constant. Otherwise, it will be O(N^2) if the string concatenation complexity is O(N).

The space complexity is O(N) where N is the number of the characters in the given unencrypted string. This is due to the fact that we have to allocate space for the encrypted string, and also the stack usage of the stack due to recursion.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Algorithm to Find Duplicate Files in System using Hash Map  C++ Coding Reference: Copy N values by using std::fill_n()  C++ Advanced Topics: 10 Questions  C++ Coding Reference: Filling a Range with a Value using std::fi  How to Get List of IP addresses in BASH using hostname and tr co  C++ Coding Reference: iota() – Setting Incrementing Values  Javascript: From Promises to Async/Await  读《杨红樱童话》有感700字  尘缘日志:忍痛割爱  写人作文我的爷爷奶奶作文800字 
评论列表
添加评论