permutation.cpp

/* Given two strings, write a method to decide if one is a 
 * permutation of the other.
 * @author: Rafayel Mkrtchyan
 * @date:   9/16/2015
 */
 
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

/** Here is the clean algorithm that completes the task.
 * However, this solution is not very optimal. The speed of
 * this approach is O(NlogN).
 */
bool permutation(std::string firstStr, std::string secondStr) {
    if (firstStr.length() != secondStr.length()) {
        return false;
    }
    std::sort(firstStr.begin(), firstStr.end());
    std::sort(secondStr.begin(), secondStr.end());
    if (firstStr.compare(secondStr) == 0) {
        return true;
    }
    return false;
 }

/** This is the second approach, which is more optional because
 * the speed is O(n), but it uses additional data structure - array
 * of integers. 
 */
bool permuation_optimal(std::string firstStr, std::string secondStr) {
    if (firstStr.length() != secondStr.length()) {
        return false;
    }
    int Checker[256] = {0};
    for (int index = 0; index < firstStr.length(); index++) {
        int value = firstStr[index];
        Checker[value]++;
    }
    for (int index = 0; index < secondStr.length(); index++) {
        int value = secondStr[index];
        Checker[value]--;
        if (Checker[value] < 0) {
            return false;
        }
    }
    return true;
}

int main() {
    std::string first = "Berkeley";
    std::string second = "keByeler";
    std::string third = "Stanforr";
    std::string fourth = "Stanford";
    std::cout << permutation(first, second) << std::endl;
    std::cout << permutation(third, fourth) << std::endl;
    std::endl (std::cout);
    std::cout << permuation_optimal(first, second) << std::endl;
    std::cout << permuation_optimal(third, fourth) << std::endl;
    return 0;
}