<릿코드> 5. Longest Palindromic Substring

거의뭐 될때까지 냈는데 ;

알고리즘 상 단축을 못시키겠어서

 

가장 큰거 부터 찾으면 그만 두게하고, 캐쉬를 사용하긴 했는데 (효용이 있는건지;)

 

가장 큰거부터 찾으니까 단축이 잘되긴했다.

 

근데 아래 답도 시간 순위 너무 낮고, 2번 제출해보니까 시간 다르길래 3번째 내니까 겨우됐음. 

 

좋은 답은 아닌듯...

class Solution {
    var cache = [[Bool]](repeating: Array(repeating: false, count: 1001), count: 1001)
    var maxLength = 0
    var maxStr: String?
    
    func longestPalindrome(_ s: String) -> String {
        let strArray = Array(s)
        
        for k in 0..<strArray.count {
            let len = strArray.count - 1 - k
            
            if maxStr != nil {
                break
            }
            
            for i in 0..<strArray.count {
                let j = i + len
                
                if j >= strArray.count {
                    break
                }
                
                if checkPalindromic(strArray,i,j) {
                    let length = j - i + 1
                    if maxLength < length {
                        maxLength = length

                        let newArray = strArray[i...j]
                        
                        maxStr = String(newArray)
                        break
                    }
                }
            }
        }
        return maxStr ?? ""
    }
    
    func checkPalindromic(_ s: Array<Character>, _ i: Int, _ j: Int) -> Bool {
        if i+1 < j-1, cache[i+1][j-1] == true, s[i] == s[j] {
            cache[i][j] = true
            return true
        } else if i+1 < j-1, cache[i+1][j-1] == true, s[i] != s[j] {
            cache[i][j] = false
            return false
        }
        
        for x in 0...j - i {

            if i + x >= j - x {
                
                cache[i][j] = true
                return true
            }
            
            if s[i + x] != s[j - x] {
                return false
            }
            
        }
        cache[i][j] = true
        return true
    }
}

//1. check if i to j is palindromic string? -
//  -> is i-1 to j+1 is palindromic?
//2. 

 

dp로 밑에 시도한건데, dp와 내가 dfs를 혼동하고 있었다.

dfs와 bruteForce도 구분 못하고 있었고.

근데 밑에껀 아직도 시간 초과임;

class Solution {
    func longestPalindrome(_ s: String) -> String {
        var st = 0
        var dt = 0
        var dp = [[Bool]](repeating: Array(repeating: false, count: 1001), count: 1001)
        var maxLength = 0
        var strArray: [Character] = []
    
        strArray = Array(s)
        
        for j in 0..<strArray.count {
            for i in 0...j {
                
                //print("\(i), \(j)")
                //j:2, i:0~2
                if i == j {
                    dp[i][j] = true
                }
                
                if i + 1 == j, strArray[i] == strArray[j] {
                    dp[i][j] = true
                } else if i+1 == j, strArray[i] != strArray[j] {
                    dp[i][j] = false
                    continue
                }
                
                if j - i + 1 > 2 {
                    dp[i][j] = (dp[i+1][j-1] && strArray[i] == strArray[j]) ? true : false  
                    if dp[i][j] == false {
                        continue
                    }
                }             
                
                let length = j - i + 1
                if length > maxLength {
                    maxLength = length
                    st = i
                    dt = j
                }
            }
        }
        return String(strArray[st...dt])
    }
}

마지막에 dp[i][j] == true로 할때만 조건주면 된다...

 

 

근데 이건 되네?? 무슨 차이지;

class Solution {
    func longestPalindrome(_ s: String) -> String {
        var st = 0
        var dt = 0
        var dp = [[Bool]](repeating: Array(repeating: false, count: 1001), count: 1001)
        var maxLength = 0
        var strArray: [Character] = []
    
        strArray = Array(s)
        
        for j in 0..<strArray.count {
            for i in 0...j {
                let judge: Bool = (strArray[i] == strArray[j])
                
                dp[i][j] = j - i > 2 ? dp[i+1][j-1] && judge : judge
                
                if (dp[i][j] && j - i + 1 > maxLength) {
                    maxLength = j - i + 1
                    st = i
                    dt = j
                }
            }
        }
        return String(strArray[st...dt])
    }
}

 

근데 이건 또 되네, 내가 진짜 조건문 정리에 약한거 같다.

class Solution {
    func longestPalindrome(_ s: String) -> String {
        var st = 0
        var dt = 0
        var dp = [[Bool]](repeating: Array(repeating: false, count: 1001), count: 1001)
        var maxLength = 0
        var strArray: [Character] = []
    
        strArray = Array(s)
        
        for j in 0..<strArray.count {
            for i in 0...j {
                
                //print("\(i), \(j)")
                //j:2, i:0~2
                if i == j {
                    dp[i][j] = true
                } else if i+1 == j, strArray[i] == strArray[j] {
                    dp[i][j] = true
                } else if i+1 == j, strArray[i] != strArray[j] {
                    dp[i][j] = false
                }else if j - i + 1 > 2 {
                    dp[i][j] = (dp[i+1][j-1] && strArray[i] == strArray[j]) ? true : false 
                }             
                
                let length = j - i + 1
                if dp[i][j], length > maxLength {
                    maxLength = length
                    st = i
                    dt = j
                }
            }
        }
        return String(strArray[st...dt])
    }
}

 

또 중요 포인트는 for를 이용한 순회의 방향을 이용해 문제를 풀 수 있다는 것이다. 나는 순회 방향으로 문제를 풀 수 있을 것이라 생각치 못했다.