다트에서 가장 긴 공통 접두사 솔루션

질문 - 어려움 - 쉬움



문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하십시오.

공통 접두사가 없으면 빈 문자열 ""을 반환합니다.

예 1:

입력: 문자열 = ["꽃","흐름","비행"]
출력: "fl"

예 2:

입력: 문자열 = ["개","raceCar","자동차"]
출력: ""
설명: 입력 문자열 사이에 공통 접두어가 없습니다.

제약:

1 <= 문자열 길이 <= 200
0 <= 문자열[i].길이 <= 200
Strings[i]는 영문 소문자로만 구성됩니다.

이론적 설명


  • S1에서 SN까지 문자열을 하나씩 반복합니다.
  • 각 문자열에 대해 0번째 인덱스, 1번째 인덱스 … i번째 인덱스를 동시에 비교하기 시작합니다.
  • i번째 인덱스 문자가 일치하지 않는 경우 알고리즘을 종료하고 LPS(1,i)를 반환합니다.
  • 그렇지 않으면 계속해서 N개의 문자열을 스캔한 후 LCP(S1…SN)를 얻을 수 있습니다.

  • 알림:-



    두 솔루션 모두 완벽하지만 첫 번째 솔루션의 문제는 실행하는 데 너무 많은 시간이 걸린다는 것입니다. 시간 초과 오류로 끝납니다.

    하지만



    두 번째 솔루션은 매력처럼 작동합니다.

    class A {
      // Not Working - Horizontal Scan
      String longestCommonPrefix(List<String> strs) {
        // Checking if the list is empty
        if (strs.length == 0 || strs.isEmpty || strs.length == '') return "";
    
    // Storing the first index value in a variable
        String prefix = strs[0];
    
    // looping the whole length of list inside the list
    // like how many strings are available
        for (var i = 0; i < strs.length; i++) {
          // storing the whole list in a variable
          String c = strs[i];
          if (c.length == 0 || prefix == "") return "";
          // setting the first index starting point in subString 0 is first string
          // AND  entire length of the remaining list
          prefix = prefix.substring(0, min(prefix.length, c.length));
          for (var j = 0; j < c.length && j < prefix.length; j++) {
            if (c[j] != prefix[j]) {
              prefix = prefix.substring(0, j);
              break;
            }
          }
        }
        return prefix;
      }
    }
    
    class B {
      // Vertical scan -Working
      String longestCommonPrefix(List<String> strs) {
        if (strs.length == 0 || strs.isEmpty || strs.length == '') return "";
    
        // looping through the length of list
        for (int i = 0; i < strs[0].length; i++) {
          // storing the value of first index and the other strings
          String c = strs[0][i];
    
          // looping again the entire length without index
          for (int j = 1; j < strs.length; j++) {
            // if the the length is same as  the length of the above loop
            //OR indexes of the list is not same as above
            if (i == strs[j].length || strs[j][i] != c)
              // returning the first index and subString starting
              // from first index and the remaining index
              return strs[0].substring(0, i);
          }
        }
        return strs[0];
      }
    }
    


    런타임: 426ms, Longest Common Prefix에 대한 Dart 온라인 제출의 100.00%보다 빠름.
    메모리 사용량: 141.9MB, Longest Common Prefix에 대한 Dart 온라인 제출물의 100.00% 미만.

    좋은 웹페이지 즐겨찾기