Created
November 15, 2020 04:18
-
-
Save jianminchen/53759eb369ce75caea6af49c17370091 to your computer and use it in GitHub Desktop.
unfinished code - 1657 - two string close
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Solution { | |
public bool CloseStrings(string word1, string word2) { | |
if(word1.Length != word2.Length) | |
return false; | |
var map = new int[26]; | |
for(int i = 0; i < 26; i++) | |
{ | |
map[i] = -1; | |
} | |
var result = runDFS(word1.ToCharArray(), word2.ToCharArray(), 0, map); | |
} | |
private bool runDFS(char[] a1, char[] a2, int start, int[] map) | |
{ | |
var length = a1.Length; | |
if(start == length) | |
return true; | |
var a1c = a1[index]; | |
var a2c = a2[index]; | |
var isSame = a1c == a2c; | |
if(isSame || (map[a1c-'a'] != -1 && map[a1c-'a'] == (a2c-'a')) | |
{ | |
return runDFS(a1, a2, start + 1); | |
} | |
else | |
{ | |
// convert a1c to a2c | |
map[a1c-'a'] = a2c - 'a'; | |
map[a2c-'a'] = a1c - 'a'; | |
var result = runDFS(a1, a2, start + 1, map); | |
if(result) | |
return true; | |
map[a1c-'a'] = -1; | |
map[a2c-'a'] = -1; | |
// swap with any letter | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment