I was coding this code snippet provided as a leetcode solution in Python but found that my variable flag isn't available.
public class Solution {
boolean flag = false;
public boolean checkInclusion(String s1, String s2) {
permute(s1, s2, 0);
return flag;
}
public String swap(String s, int i0, int i1) {
if (i0 == i1)
return s;
String s1 = s.substring(0, i0);
String s2 = s.substring(i0 + 1, i1);
String s3 = s.substring(i1 + 1);
return s1 + s.charAt(i1) + s2 + s.charAt(i0) + s3;
}
void permute(String s1, String s2, int l) {
if (l == s1.length()) {
if (s2.indexOf(s1) >= 0)
flag = true;
} else {
for (int i = l; i < s1.length(); i++) {
s1 = swap(s1, l, i);
permute(s1, s2, l + 1);
s1 = swap(s1, l, i);
}
}
}
}
This is how I rewrote it in Python together with the checks. What I did was move the helper functions to be part of the checkInclusion function so that the helper functions can run within the context of, for lack of a better word, "main" function. What I noticed is that my assertions fail. In trying to debug, I tried to print out the flag variable but nothing was printed out.
from typing import List
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
def swap(string: str, left: int, right: int) -> str:
stringList = list(string)
stringList[left], stringList[right] = stringList[right], stringList[left]
return "".join(stringList)
def permute(string:str, left: int, right: int, permutations: List[int]) -> List[int]:
"""left and right are indices for the string"""
if left == right:
permutations.append(string)
return permutations
else:
for i in range(left, right+1):
swapped = swap(string, left, i)
permute(swapped, left+1, right, permutations)
return permutations
permutations = permute(s1, 0, len(s1)-1, [])
# print("permutations =", permutations)
for permutation in permutations:
if permutation in s2:
return True
return False
# brute force - NOT creating a list of the permutations
# n = len(s1)
# m = len(s2)
# Time : O(n! + nm) - creating the permutations and nm for
# comparing the s1 in s2. Depends on relative size of s1 and s2
# to determine what dominates
# Space: O(n!) - n! for the list of permutations, O(n x n) for the
# recursion tree depth and length of the string but n! dominates
# for large n.
from typing import List
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
flag = False
def swap(string: str, left: int, right: int) -> str:
stringList = list(string)
stringList[left], stringList[right] = stringList[right], stringList[left]
return "".join(stringList)
def permute(s1: str, s2: str, pos: int) -> None:
print("flag in permute =", flag)
if pos == len(s1):
print("flag in if statement", flag)
if s2.find(s1) > -1:
flag = True
else:
for i in range(1, len(s1)):
s1 = swap(s1, pos, i)
permute(s1, s2, pos+1)
s1 = swap(s1, pos, i)
permute(s1, s2, 0)
return flag
sol = Solution()
s1 = "x"
s2 = "ab"
assert sol.checkInclusion(s1, s2) == True
s1 = "a"
s2 = "ab"
print(sol.checkInclusion(s1, s2))
assert sol.checkInclusion(s1, s2) == True
s1 = "ab"
s2 = "eidbaooo"
assert sol.checkInclusion(s1, s2) == True
s1 = "ab"
s2 = "eidboaoo"
assert sol.checkInclusion(s1, s2) == False
The error I got doesn't print out flag.
Traceback (most recent call last):
File "567. Permutation in String.py", line 75, in <module>
assert sol.checkInclusion(s1, s2) == True
File "567. Permutation in String.py", line 68, in checkInclusion
permute(s1, s2, 0)
File "567. Permutation in String.py", line 57, in permute
print("flag in permute =", flag)
UnboundLocalError: local variable 'flag' referenced before assignment
Although I would like to know how to make a better conversion into Python, I feel I am missing a crucial bit of information on why flag appears to be assigned before it is referenced.
