Problem statement

Given two strings s and t, determine if they are isomorphic. Two strings s and t are isomorphic if the characters in s can be replaced to get t. All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself. s and t consist of any valid ascii character.

Solution

Code

Brute force

#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

bool checkPair_slow(vector<int> arr, int target) {

  for (int i = 0; i < arr.size(); i++) {
    for (int j = i; j < arr.size(); j++) {
      if (arr[i] + arr[j] == target)
        return true;
    }
  }

  return false;
}

int main() {

  vector<int> arr = {3, 2, 7, 6, 5, 3, 2, 7, 12, 15, 1};

  printf(checkPair(arr, 54) ? "t" : "f");
  printf("\n");

  return 0;
}

Hashmap

#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

bool checkPair(vector<int> arr, int target) {
  unordered_map<int, int> umap;
  for (int i = 0; i < arr.size(); i++) {
    if (umap.find(target - arr[i]) != umap.end()) {
      return true;
    } else {
      umap[arr[i]] = i;
    }
  }
  return false;
}

int main() {

  vector<int> arr = {3, 2, 7, 6, 5, 3, 2, 7, 12, 15, 1};

  printf(checkPair(arr, 54) ? "t" : "f");
  printf(checkPair_slow(arr, 54) ? "t" : "f");
  printf("\n");

  return 0;
}